Surface Embedding of Non-Bipartite k-Extendable Graphs

DOI10.4208/AAM.OA-2021-0008MaRDI QIDQ5865906zbMATH OpenFDO

Authors Hongliang Lu, David G. L. Wang

Publication date 10 June 2022

Published in Annals of Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

matching extensionnon-bipartite graphsurface embedding

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We find the minimum number $k=m{u}^{\prime }(Sigma)$ for any surface $Sigma$, such that every $Sigma$-embeddable non-bipartite graph is not $k$-extendable. In particular, we construct the so-called bow-tie graphs $$, and show that they are $3$-extendable. This confirms the existence of an infinite number of $3$-extendable non-bipartite graphs which can be embedded in the Klein bottle.

Recommendations

• Surface embedding of \((n,k)\)-extendable graphs
• scientific article; zbMATH DE number 772738
• The (\(n\), \(k\))-extendable graphs in surfaces
• A characterization of embeddability of graphs on surfaces
• On graphs embedded in a surface
• Embedding graphs on surfaces
• Surface embeddability of graphs via homology
• Surface embeddings of the Klein and the Möbius–Kantor graphs
• On the connectivity of graphs embedded in surfaces
• scientific article; zbMATH DE number 1960647

Cites work

• A polynomial algorithm for the extendability problem in bipartite graphs
• A short proof of K�nig's matching theorem
• Bestimmung der Maximalzahl der Nachbargebiete auf nicht-orientierbaren Flächen
• Connectivity of \(k\)-extendable graphs with large \(k\).
• Extending matchings in graphs: A survey
• Graph Factors and Matching Extensions
• scientific article; zbMATH DE number 434908 (Why is no real title available?)
• scientific article; zbMATH DE number 4006288 (Why is no real title available?)
• scientific article; zbMATH DE number 4047749 (Why is no real title available?)
• scientific article; zbMATH DE number 3179262 (Why is no real title available?)
• scientific article; zbMATH DE number 4118405 (Why is no real title available?)
• scientific article; zbMATH DE number 5593479 (Why is no real title available?)
• scientific article; zbMATH DE number 3241107 (Why is no real title available?)
• scientific article; zbMATH DE number 3310750 (Why is no real title available?)
• Matching extension and the genus of a graph
• Matching theory
• Note on Hamilton Circuits
• On n-extendable graphs
• On the matching extendability of graphs in surfaces
• Recent Progress in Matching Extension
• SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM
• Surface embedding of \((n,k)\)-extendable graphs
• The Cartesian product of a \(k\)-extendable and an \(l\)-extendable graph is \((k+l+1)\)-extendable
• The Factorization of Linear Graphs
• The matching extendability of surfaces

Cited in

(5)

• The (\(n\), \(k\))-extendable graphs in surfaces
• Checkerboard embeddings of *-graphs into nonorientable surfaces
• Surface embedding of \((n,k)\)-extendable graphs
• Surface embeddings of the Klein and the Möbius–Kantor graphs
• 2-extendability and \(k\)-resonance of non-bipartite Klein-bottle polyhexes

This page was built for publication: Surface Embedding of Non-Bipartite $k$-Extendable Graphs

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