Some necessary conditions for a graph to be Hamiltonian (Q2482325)

Let \(G\) be a graph on \(v\) vertices and \(s\) edges, and let \(S= \{a_1,\dots, a_n\}\) be a set of \(n\leq s\) symbols. Associate with each edge \(e\) a symbol of \(S\) such that two edges \(e\), \(f\) are associate with the same symbol only if there is an automorphism of \(G\) mapping \(e\) onto \(f\). For every vertex \(x\) define the spectrum \(S(x)\) to be the \((1\times n)\)-matrix whose \(i\)th entry is the number of edges incident with \(x\) and associated with \(a_i\). Two vertices are equivalent if they have the same spectrum. Let \(V_1,\dots, V_m\) be the equivalence classes, and denote by \(S_1,\dots, S_m\) the corresponding spectra. The spectral matrix \(M\) of \(G\) is the \((m\times n)\)-matrix whose \(i\)th row is \(S_i\); the extended spectral matrix \(M'\) of \(G\) arises by augmenting \(M\) by an \((n+1)\)th column whose entries are all \(1\). The difference spectral matrix \(M''\) is the \(((m- 1)\times n)\)-matrix whose \(j\)th row is \(S_1- S_j\), \(2\leq j\leq m\). The authors prove 1. If \(G\) is Hamiltonian, then \(r(M)= r(M')\). 2. If \(G\) is Hamiltonian, then \(r(M')\leq n\). 3. If \(G\) is Hamiltonian and not all spectra are the same, then \(r(M'')< n\). Thus, if \(m= n+1\) then \(\det M''= 0\). The authors demonstrate these results by looking at various examples as well.