Locally finite, planar, edge-transitive graphs

Jack E. Graver, Mark E. Watkins

Research output: Contribution to journalArticlepeer-review

43 Scopus citations

Abstract

A complete presentation is given of the class g of locally finite, edge-transitive, 3-connected planar graphs. They are classified according to (1) the number of ends: zero (for the nine finite members), 1, 2, or 2א0; (2) their Petrie type, and (3) the local action of their automorphism groups. A Petrie walk in a plane graph is a walk with the property every two consecutive edges are incident with a common face but no three consecutive edges have this property. It is shown that the Petrie walks in members of g are either elementary circuits of even length or double rays. These graphs are of circuit type, line type, or mixed type according as the two Petrie walks through each edge are both circuits, both double rays, or one of each, respectively. The 14 possible combinations of the stabilizers of the edges, vertices, faces, and Petrie walks of graphs in g are computed. Exactly eight of these combinations are realizable in g; they are highly correlated with both the number of ends and the Petrie type. A member of g is ordinary if all vertex-face reflections are present in its automorphism group; otherwise it is extraordinary. B. Grünbaum and G.C. Shephard have determined the permissible valences and covalences of the 1-ended graphs in g, and M.E. Watkins has done the same for its 2-ended members. All members of g with at most two ends are ordinary. The existence of infinitely-ended graphs in g is settled affirmatively, and an explicit method is presented which permits the construction of all infinitely-ended, ordinary members and many extraordinary members of g. All multiended, ordinary graphs are of mixed type, and their Petrie circuits are shortest circuits that separate ends. All infinitely-ended graphs in g of line type are extraordinary; several examples are given. Ordinary graphs admit no infinite faces, and it is conjectured that the same holds for extraordinary graphs.

Original languageEnglish (US)
Pages (from-to)1-75
Number of pages75
JournalMemoirs of the American Mathematical Society
Issue number601
DOIs
StatePublished - Mar 1997

Keywords

  • Automorphism group
  • Double ray
  • Edge-transitive
  • Ends of a graph
  • Locally finite graph
  • Petrie walk
  • Planar
  • Plane graph

ASJC Scopus subject areas

  • General Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Locally finite, planar, edge-transitive graphs'. Together they form a unique fingerprint.

Cite this