Graphs with polynomial growth are covering graphs
type: Item
instance of: scholarly article
title: Graphs with polynomial growth are covering graphs
zbMATH Open document ID: 0764.05034
DOI: 10.1007/BF02349960
author: Chris Godsil
author: N. Seifert
published in: Graphs and Combinatorics
publication date: 1993-01-16T00:00:00Z
review text: Let \(X(V,E)\) be a simple undirected locally finite graph with vertex set \(V(X)\) and edge set \(E(X)\). The growth function of \(X\), with respect to a vertex \(v\in V(X)\) is defined by \(f_ X(v,0)=1\) and \(f_ X(v,n)=|\{w\in V(X)| d(v,w)\leq n\}|\), \(n\in N\), where \(d(v,w)\) denotes the distance between \(v\) and \(w\). If \(X(V,E)\) has a transitive automorphism group, then the growth function is denoted by \(f_ X(n)\). \(X(V,E)\) has polynomial growth if there are constants \(c\), \(d\) such that \(f_ X(n)\leq cn^ d\) for all integers \(n\geq 1\). Let \(\varphi\), \(\varphi:X_ 1\to X_ 2\), denote a homomorphism and let \(S(v)\), \(v\in V(X_ 1)\), be the star consisting of \(v\) and all edges incident to \(v\). If \(\varphi(S(v))\) is isomorphic to \(S(v)\), for every \(v\in V(X_ 1)\), \(X_ 1\) is called a covering graph of \(X_ 2\). The authors prove that there are infinitely many finite graphs \(Y_ 1\), \(Y_ 2,\dots\) such that \(X\) is a covering graph of each of these graphs and every \(Y_ k\), \(k\geq 2\), is covering graph of the graphs \(Y_ 1,\dots,Y_{k-1}\).
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 93439
zbMATH Keywords: \(s\)-transitive graph
zbMATH Keywords: locally finite graph
zbMATH Keywords: growth function
zbMATH Keywords: distance
zbMATH Keywords: transitive automorphism group
zbMATH Keywords: polynomial growth
zbMATH Keywords: covering graph
reviewed by: Ulrike Baumann
MaRDI profile type: Publication
cites work: The Degree of Polynomial Growth of Finitely Generated Nilpotent Groups
cites work: Q4770409
cites work: Automorphisms of graphs and coverings
cites work: A note on bounded automorphisms of infinite graphs
cites work: Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
cites work: Über unendliche Wege in Graphen
cites work: Q4141974
cites work: Q4102039
cites work: Properties of graphs with polynomial growth
cites work: GRAPHS WITH POLYNOMIAL GROWTH
cites work: Q3687182
cites work: The nonexistence of 8-transitive graphs
full work available at URL: https://doi.org/10.1007/bf02349960
OpenAlex ID: W1971127991
description: scientific article; zbMATH DE number 93439