Enumerating planar locally finite Cayley graphs. (Q2571720): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 4 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1968071742 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: cs/0309017 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Congruent Graphs and the Connectivity of Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On non-Euclidean crystallographic groups / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 12:44, 11 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Enumerating planar locally finite Cayley graphs. |
scientific article |
Statements
Enumerating planar locally finite Cayley graphs. (English)
0 references
14 November 2005
0 references
Cayley graphs are represented in the paper under review by finite state automata called labelling schemes together with a local geometric invariant called a type vector. It is shown that there exists a bijection between this representation and the class of locally finite planar Cayley graphs. The main result is an enumeration theorem, namely that for \(n\geq 2\) all planar locally finite Cayley graphs having internal degree \(n\) can be effectively enumerated, along with one representative presentation. For each Cayley graph belonging to this class there exists an algorithm able to build any finite ball of the graph, which leads to algorithms solving the word problem. Complete lists of locally finite Cayley graphs of degree 3 and 4, together with presentation, type vector, and figure for each class, are given in the appendix.
0 references
vertex-transitive graphs
0 references
Cayley graphs
0 references
planar graphs
0 references
tilings
0 references
labelling schemes
0 references
finite state automata
0 references
finite presentations
0 references
solvable word problem
0 references