Families of regular graphs in regular maps

Steve Wilson

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

The question of when a given graph can be the underlying graph of a regular map has roots a hundred years old and is currently the object of several threads of research. This paper outlines this topic briefly and proves that a product of graphs which have regular embeddings also has such an embedding. We then present constructions for members of three families: (1) circulant graphs, (2) wreath graphs W(k, n), whose vertices are ordered pairs (i, j), 0 ≤ i < k, 0 ≤ j < n, and whose edges are all possible (i, j) - (i + 1, j′), and (3) depleted wreath DW(k, n), the subgraph of W(k, n) left by removing all edges in which j = j′. We open the question of multiplicity of occurrence and we list the underlying graphs of rotary maps with no more than 50 edges.

Original languageEnglish (US)
Pages (from-to)269-289
Number of pages21
JournalJournal of Combinatorial Theory. Series B
Volume85
Issue number2
DOIs
StatePublished - 2002

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Families of regular graphs in regular maps'. Together they form a unique fingerprint.

Cite this