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

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

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

• scientific article; zbMATH DE number 3831963 (Why is no real title available?)
• scientific article; zbMATH DE number 3499787 (Why is no real title available?)
• 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
• 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)

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