Edge‐maximal graphs on orientable and some nonorientable surfaces

DOI10.1002/JGT.22705zbMATH Open1522.05062arXiv1911.02666OpenAlexW3177562069MaRDI QIDQ6056751FDOQ6056751

Authors: James E. Davies, Florian Pfender 

Publication date: 4 October 2023

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

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.

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

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

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)

Cites Work

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

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)