In this paper, we explore some interesting applications of the matrix tree theorem. In particular, we present a combinatorial interpretation of a distribution of \((n-1)^{n-1}\), in the context of uprooted spanning trees of the complete graph \(K_{n}\), which was previously obtained by Chauve–Dulucq–Guibert. Additionally, we establish a combinatorial explanation for the distribution of \(m^{n-1}n^{m-1}\), related to spanning trees of the complete bipartite graph \(K_{m,n}\), which seems new. Furthermore, we extend this study to the graph \(K_{n}\setminus \{e_{1,n}\}\), obtained by deleting an edge from \(K_n\), and derive a new identity for the number of its uprooted spanning trees.

The domatic number of a graph is the maximum number of pairwise disjoint dominating sets admitted by the graph. We introduce a game based around this graph invariant. The domatic number game is played on a graph \(G\) by two players, Alice and Bob, who take turns selecting a vertex and placing it into one of \(k\) sets. Alice is trying to make each of these sets into a dominating set of \(G\) while Bob’s goal is to prevent this from being accomplished. The maximum \(k\) for which Alice can achieve her goal when both players are playing optimal strategies, is called the game domatic number of \(G\). There are two versions of the game and two resulting invariants depending on whether Alice or Bob is the first to play. We prove several upper bounds on these game domatic numbers of arbitrary graphs and find the exact values for several classes of graphs including trees, complete bipartite graphs, cycles and some narrow grid graphs. We pose several open problems concerning the effect of standard graph operations on the game domatic number as well as a vexing question related to the monotonicity of the number of sets available to Alice.

Sparse magic squares are a generalization of magic squares and can be used to the magic labeling of graphs. An \(n\times n\) array based on \(\mathcal{X}\)\(=\{0,1,\cdots,nd\}\) is called a sparse magic square of order \(n\) with density \(d\) (\(d<n\)), denoted by SMS\((n,d)\), if each non-zero element of \(\mathcal{X}\) occurs exactly once in the array, and its row-sums, column-sums and two main diagonal sums is the same. An SMS\((n,d)\) is called pandiagonal (or perfect) denoted by PSMS\((n,d)\), if the sum of all elements in each broken diagonal is the same. A PSMS\((n,d)\) is called regular if there are eactly \(d\) positive entries in each row, each column and each main diagonal. In this paper, some construction of regular pandigonal sparse magic squares is provided and it is proved that there exists a regular PSMS\((n,6)\) for all positive integer \(n\equiv 5 \pmod{6}\), \(n>6\).

Two graphs are said to be \(Q\)-cospectral (respectively, \(A\)-cospectral) if they have the same signless Laplacian (respectively, adjacency) spectrum. A graph is said to be \(DQS\) (respectively, \(DAS\)) if there is no other non-isomorphic graphs \(Q\)-cospectral (respectively, \(A\)-cospectral) with it. A tree on \(n\) vertices with maximum degree \(d_1\) is called starlike and denoted by \(ST(n, d_1)\), if it has exactly one vertex with the degree greater than 2. A tree is called double starlike if it has exactly two vertices of degree greater than 2. If we attach \(p\) pendant vertices (vertices of degree 1) to each of pendant vertices of a path \(P_n\), the the resulting graph is called the double starlike tree \(H_n(p,p)\). In this article, we prove that all double starlike trees \(H_n(p,p)\) are \(DQS\), where \(p\geq 1, n\geq 2\) and \(p\) denotes . In addition, by a simple method, we show that all starlike trees are \(DQS\) excluding \(K_{1,3}=ST(4,3)\).