Wug-snake graphs and Markov numbers of matrix semigroups

Classically, Markov numbers are recovered as perfect matching numbers of domino snake graphs. We extend this correspondence to matrix semigroups by introducing weighted universal generalised snake graphs, or wug-snake graphs for short. These are weighted bipartite graphs whose perfect matching sequences encode linear recurrences. We associate to each wug-snake graph a continuant matrix and prove that its determinant equals the weighted perfect matching number. We use this construction to define polymino wug-tiles for matrices and show that their determinants compute Markov-Davenport forms. Consequently, algebraic and geometric Markov numbers of matrices, and of matrix semigroups, can be expressed through perfect matchings. We develop the corresponding Frobenius maps for semigroups and study examples recovering classical Markov numbers, weighted PLLS-sequences, and higher-dimensional lattice realisations.