Parsons graphs of matrices on \(\mathcal Z_{p^ n}\) (Q1910562)

The paper discusses the problem of connectivity of Parsons graphs. This problem was proposed by \textit{J. Zaks} [Discrete Math. 78, No. 1/2, 187-193 (1989; Zbl 0747.05060)]. Let \(R\) be a finite field with \(q\) elements and \(\text{SL}_d (R)\) the linear group on \(R\) of dimension \(d\). The Parsons graph \(T_b (d,q)\) is defined as follows. The vertex set \(V\) consists of all matrices over \(R\) with determinant equal to 1, two matrices \(A\) and \(B\) form an edge iff \(\text{det} (A - B) = b\). It is proved that every Parsons graph, except for \(T_1 (2,2)\) and \(T_2 (2,3)\), is connected. The notion of Parsons graph is generalised for rings \(\mathbb{Z}_{p^n}\) where \(p\) is a prime. It is proved that all generalised Parsons graphs are connected, with exception of \(T_{2k + 1} (2,2^n)\) for \(k = 0\), \(1, \dots, 2^{n - 1}\), and \(T_{3k + 2} (2,3^n)\) for \(k = 0\), \(1, \dots, 3^{n - 1} - 1\).