Graphs with polynomial growth are covering graphs (Q1199120): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf02349960 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1971127991 / rank | |||
Normal rank |
Latest revision as of 09:41, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Graphs with polynomial growth are covering graphs |
scientific article |
Statements
Graphs with polynomial growth are covering graphs (English)
0 references
16 January 1993
0 references
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}\).
0 references
\(s\)-transitive graph
0 references
locally finite graph
0 references
growth function
0 references
distance
0 references
transitive automorphism group
0 references
polynomial growth
0 references
covering graph
0 references