Graph recurrence

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Review text

This paper is related to the graph isomorphism problem and deals with particular types of graph invariants called graph recurrence sequences. Let \(G\) be a graph of order \(n\) with adjacency matrix \(A\). Then each vector \(x_0\in \mathbb{R}^n\) determines a graph recurrence sequence \(\{x_i\}_{i=1}^n\) whose terms satisfy the recurrence \(x_{t+1}=A x_t\), \(t\geq 0\). If this sequence determines \(G\), then \(G\) is said to be determined by \(x_0\). If \(G\) is determined by \(e_i\), the vector with 1 at coordinate \(i\) and all other coordinates 0, then \(G\) is said to be determined by vertex \(i\). Complete graphs, complete bipartite graphs, cycles, wheels and trees are all shown to be determined by a single vertex. The author also proves that if \(G\) is determined by one of its vertices or if the vectors in some recurrence sequence of \(G\) span \(\mathbb{R}^n\), then \(G\) can be distinguished from any other graph in polynomial time. Two other topics related to graph recurrence sequences, \(m\)-equivalence of graphs and separating vertices, are introduced in the paper and their relevance to the graph isomorphism problem is explored. Numerous open questions related to these topics are posed throughout the paper.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Graph recurrence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1869026)