Parsons graphs of matrices (Q1812760): Difference between revisions

Parsons graphs are introduced with respect to the problem of finding the maximal set of matrices \(A_ 1,\dots,A_ m\) over a finite field with property \(\text{det} (A_ i)=1\) for all \(1\leq i\leq m\) and \(\text{det} (A_ i-A_ j)=1\) for all \(1\leq i<j\leq m\). The vertex set of a Parson graph \(T_ b(d,q)\) is the collection of all \(d\times d\) matrices \(A\) (\(d\) is even) over a finite field \(F\) with \(q\) elements for which \(\text{det} (A)=1\). Two vertices \(A\), \(B\) are adjacent in \(T_ b(d,q)\) iff \(\text{det} (A-B)=b\). There are shown some important properties of \(T_ b(d,q)\) as the vertex transitivity and some facts about the structure of these graphs. For the case \(b=0\) it is shown connectivity for all \(d\geq 4\). The author conjectures that every Parsons graph except for \(T_ 1(2,2)\) is connected and for \(d=2\), \(q\geq 3\) \(T_ b(d,q)\) has a 1-factor and is Hamiltonian.