Graph recurrence (Q1869026)

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.