Edge‐maximal graphs on orientable and some nonorientable surfaces

DOI10.1002/JGT.22705MaRDI QIDQ6056751zbMATH OpenOpenAlexFDO

Authors James E. Davies, Florian Pfender

Publication date 4 October 2023

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

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

zbMATH Keywords

graph embeddingimpure graphs

Mathematics Subject Classification ID

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

Abstract: We study edge-maximal, non-complete graphs on surfaces that do not triangulate the surface. We prove that there is no such graph on the projective plane $mathbb{N}_1$, $K_7-e$ is the unique such graph on the Klein bottle $mathbb{N}_2$ and $K_8-E(C_5)$ is the unique such graph on the torus $mathbb{S}_1$. In contrast to this for each $gge2$ we construct an infinite family of such graphs on the orientable surface $mathbb{S}_g$ of genus $g$, that are $lfloorfracg2floor$ edges short of a triangulation.

Recommendations

• Edge-maximal graphs on surfaces
• Locally-maximal embeddings of graphs in orientable surfaces
• On the maximum order of graphs embedded in surfaces
• scientific article; zbMATH DE number 1150354
• Maximal orientations of graphs
• Edge‐maximal (k, i)‐graphs
• A note on strong embeddings of maximal planar graphs on non-orientable surfaces
• On graphs with the maximum edge metric dimension
• Oriented matroids and complete-graph embeddings on surfaces
• On graphs, which can be drawn on an orientable surface with small number of intersections on an edge

Cites work

• A Maximal Toroidal Graph which is not a Triangulation.
• A minimum-vertex triangulation
• Edge-maximal graphs on surfaces
• Face distributions of embeddings of complete graphs
• Graphs on surfaces
• Homomorphiesätze für Graphen
• scientific article; zbMATH DE number 3831963 (Why is no real title available?)
• scientific article; zbMATH DE number 3499787 (Why is no real title available?)
• Knots and links in spatial graphs
• Locally Hamiltonian graphs and minimal size of maximal graphs on a surface
• Maximal knotless graphs
• Minimal triangulations on orientable surfaces
• Non-separating planar graphs
• On the purity of minor-closed classes of graphs
• The genus of subgraphs of \(K_ 8\)
• Wie man die geschlossenen nichtorientierbaren Flächen in möglichst wenig Dreiecke zerlegen kann

Cited in

(6)

• Covering projective planar graphs with three forests
• On the dichromatic number of surfaces
• Upper bounds on the maximum degree of class two graphs on surfaces
• Edge partition of graphs embeddable in the projective plane and the Klein bottle
• Edge-maximal graphs on surfaces
• Robust connectivity of graphs on surfaces

This page was built for publication: Edge‐maximal graphs on orientable and some nonorientable surfaces

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