Algorithmic aspects of arithmetical structures (Q2668075)

This paper studies the set of arithmetical structures on non-negative integer \(n\times n\)-matrices \(L\) with zero diagonal, defined as follows: \[ \mathcal{A}(L)=\left\{(\mathbf{d},\mathbf{r})\in\mathbb{N}_+^n\times \mathbb{N}_+^n \, | \, (\textrm{Diag}(\mathbf{d})-L)\mathbf{r}^t = \mathbf{0}^t \, \textrm{and} \gcd(r_1,\dots,r_n)=1\right\}. \] This is a finite set, and the main result of the article is Algorithm 3.4, which computes the set \(\mathcal{D}(L)\) defined below, given the matrix \(L\) as input. \[ \mathcal{D}(L)=\left\{\mathbf{d}\in \mathbb{N}_+^n \, | \, (\mathbf{d},\mathbf{r})\in\mathcal{A}(L)\right\}. \] In order to develop this algorithm, the author's introduce the class of \textit{quasi \(M\)-matrices}, which are a simple generalization of \(M\)-matrices. The paper concludes by using the algorithm to provide computational evidence for the following conjecture:\\ Conjecture: Let \(G\) be a simple graph with \(n\) vertices. Then \[ |\mathcal{A}(P_n)|\le |\mathcal{A}(G)|\le|\mathcal{A}(K_n)|, \] where \(P_n\) and \(K_n\) are the path and complete graph on \(n\) vertices respectively. Here, \(\mathcal{A}(G)=\mathcal{A}(L_G)\) denotes the set of arithmetical structures on the Laplacian matrix of the graph \(G\).