Disproof of a conjecture on the existence of the path-recursive period for a connected graph (Q1587898): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Xue-rong Yong / rank | |||
Property / author | |||
Property / author: Xue-rong Yong / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q123284911 / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Path polynomials of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the polynomial of a path / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Path-positive graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Path positivity and infinite Coxeter groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3359644 / rank | |||
Normal rank |
Latest revision as of 10:47, 3 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Disproof of a conjecture on the existence of the path-recursive period for a connected graph |
scientific article |
Statements
Disproof of a conjecture on the existence of the path-recursive period for a connected graph (English)
0 references
4 June 2001
0 references
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.
0 references
adjacency matrix
0 references
eigenvalue
0 references
path polynomial
0 references
path-recursive period
0 references