Disproof of a conjecture on the existence of the path-recursive period for a connected graph (Q1587898): Difference between revisions

Let \(P_{k}(\lambda)=\det(\lambda I- P_{k})\) denote the characteristic polynomial of a path \(P_{k}\) on \(k\) vertices with \(k-1\) edges. If \(A\) is the adjacency matrix of a graph \(G\) and \(P_{k}(A)\) is obtained by substituting \(A\) for \(\lambda \) in \(P_{k}(\lambda)\), then the \(P_{k}(A)\) for \(k=1,2,\ldots \) are called the path polynomials for \(G\). (By convention \(P_{0}(A)=I\).) If there exists a positive integer \(m\geq 2\), such that \(P_{m}(A)= [P_{m-2}(A)+I]+I\) and \(P_{m+1}(A)= P_{m-1}(A)+A\) then the least such integer \(m\) is called the path-recursive period of \(G\). It had been conjectured that every connected graph has a path-recursive period. In this paper, the authors give an elementary argument to disprove the conjecture.