Graph recurrence
type: Item
instance of: scholarly article
title: Graph recurrence
zbMATH Open document ID: 1022.05051
DOI: 10.1016/S0195-6698(02)00136-1
author: Andrew Vince
published in: European Journal of Combinatorics
publication date: 2003-04-09T00:00:00Z
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.
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 1895795
zbMATH Keywords: isomorphism
zbMATH Keywords: recurrence
zbMATH Keywords: adjacency matrix
reviewed by: Robert R. Molina
MaRDI profile type: Publication
cites work: Random Graph Isomorphism
cites work: Q3320418
cites work: An Efficient Algorithm for Graph Isomorphism
cites work: Q4148000
cites work: A Linear Time Algorithm for Deciding Interval Graph Isomorphism
cites work: Isomorphism of graphs of bounded valence can be tested in polynomial time
cites work: Separation index of a graph
full work available at URL: s0195-6698(02)00136-1
OpenAlex ID: W2912902786
description: scientific article; zbMATH DE number 1895795