Face distributions of embeddings of complete graphs

DOI10.1002/JGT.22655MaRDI QIDQ6055941zbMATH OpenOpenAlexFDO

Authors Timothy Sun

Publication date 29 September 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.02092

zbMATH Keywords

current graphsmap color theoremtopological graph theory

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: A longstanding open question of Archdeacon and Craft asks whether every complete graph has a minimum genus embedding with at most one nontriangular face. We exhibit such an embedding for each complete graph except $K_8$, the complete graph on 8 vertices, and we go on to prove that no such embedding can exist for this graph. Our approach also solves a more general problem, giving a complete characterization of the possible face distributions (i.e. the numbers of faces of each length) realizable by minimum genus embeddings of each complete graph. We also tackle analogous questions for nonorientable and maximum genus embeddings.

Recommendations

• Minimum genus embeddings of the complete graph
• Doubly even orientable closed 2-cell embeddings of the complete graph
• Face size and the maximum genus of a graph. I: Simple graphs
• Exponential families of nonisomorphic nonorientable genus embeddings of complete graphs
• Face 2-colourable triangular embeddings of complete graphs

Cites work

• A minimum-vertex triangulation
• Another proof of the map color theorem for nonorientable surfaces.
• Exponential families of non-isomorphic non-triangular orientable genus embeddings of complete graphs.
• Exponential families of non-isomorphic triangulations of complete graphs
• Generalized Embedding Schemes
• Graphs of groups on surfaces. Interactions and models
• Hierarchy for imbedding-distribution invariants of a graph
• How to determine the maximum genus of a graph
• scientific article; zbMATH DE number 2186718 (Why is no real title available?)
• scientific article; zbMATH DE number 4006288 (Why is no real title available?)
• scientific article; zbMATH DE number 3450230 (Why is no real title available?)
• Le problème des régions voisines sur les surfaces closes orientables
• On the maximum genus of a graph
• On the number of nonisomorphic orientable regular embeddings of complete graphs
• SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM
• Solution of the Heawood map-coloring problem—case 11
• Solution of the heawood map-coloring problem—Cases 3, 5, 6, and 9
• The genus of \(K_n-K_2\)
• The genus of nearly complete graphs-case 6
• Three nonisomorphic triangulations of an orientable surface with the same complete graph
• Triangular embeddings of complete graphs from graceful labellings of paths

Cited in

(14)

• Face size and the maximum genus of a graph. I: Simple graphs
• Face covers and the genus problem for apex graphs
• The genus of complete 3-uniform hypergraphs
• Settling the genus of the n-prism
• Face-width of embedded graphs
• scientific article; zbMATH DE number 1161284 (Why is no real title available?)
• On the local genus distribution of graph embeddings
• scientific article; zbMATH DE number 4185634 (Why is no real title available?)
• Graph Drawing
• Edge‐maximal graphs on orientable and some nonorientable surfaces
• The connectivity of the dual
• Jungerman ladders and index 2 constructions for genus embeddings of dense regular graphs
• Asymptotics of local face distributions and the face distribution of the complete graph
• An optimal construction for complete graph embeddings with duals of low connectivity

This page was built for publication: Face distributions of embeddings of complete graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6055941)