Edge-maximal graphs on surfaces

DOI10.4153/CJM-2017-028-0MaRDI QIDQ4584324zbMATH OpenOpenAlexFDO

Authors David R. Wood, Colin McDiarmid

Publication date 30 August 2018

Published in Canadian Journal of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

embeddingsurface

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 prove that for every surface $Sigma$ of Euler genus $g$, every edge-maximal embedding of a graph in $Sigma$ is at most $O(g)$ edges short of a triangulation of $Sigma$. This provides the first answer to an open problem of Kainen (1974).

Recommendations

• Edge‐maximal graphs on orientable and some nonorientable surfaces
• On the edge reconstruction of graphs embedded in surfaces. III
• Locally Hamiltonian graphs and minimal size of maximal graphs on a surface
• Locally-maximal embeddings of graphs in orientable surfaces
• On the edge-reconstruction of graphs embedded in surfaces. IV

Cited in

(10)

• On the purity of minor-closed classes of graphs
• Locally Hamiltonian graphs and minimal size of maximal graphs on a surface
• Upper bounds on the maximum degree of class two graphs on surfaces
• 3-edge-connected embeddings have few singular edges
• Robust connectivity of graphs on surfaces
• Classes of graphs embeddable in order-dependent surfaces
• Edge‐maximal graphs on orientable and some nonorientable surfaces
• On the maximum number of cliques in a graph embedded in a surface
• On the connectivity of graphs embedded in surfaces. II
• Densely embedded graphs

This page was built for publication: Edge-maximal graphs on surfaces

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