Surface embedding of (n,k)-extendable graphs

DOI10.1016/J.DAM.2014.08.003MaRDI QIDQ477346zbMATH OpenOpenAlexFDO

Authors Hongliang Lu, David G. L. Wang

Publication date 3 December 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Euler contributionfactor-criticalitymatching extendabilitysurface 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: This paper is concerned with the surface embedding of matching extendable graphs. There are two directions extending the theory of perfect matchings, that is, matching extendability and factor-criticality. In solving a problem posed by Plummer, Dean (The matching extendability of surfaces, J. Combin. Theory Ser. B 54 (1992), 133--141) established the fascinating formula for the minimum number $k=mu(Sigma)$ such that every $Sigma$-embeddable graph is not $k$-extendable. Su and Zhang, Plummer and Zha found the minimum number $n=ho(Sigma)$ such that every $Sigma$-embeddable graph is not $n$-factor-critical. Based on the notion of $(n,k)$-graphs which associates these two parameters, we found the formula for the minimum number $k=mu(n,Sigma)$ such that every $Sigma$-embeddable graph is not an $(n,k)$-graph. To access this two-parameter-problem, we consider its dual problem and find out $mu(n,Sigma)$ conversely. The same approach works for rediscovering the formula of the number $ho(Sigma)$.

Recommendations

• The (\(n\), \(k\))-extendable graphs in surfaces
• The matching extendability of surfaces
• On the matching extendability of graphs in surfaces
• scientific article; zbMATH DE number 871171
• Surface Embedding of Non-Bipartite $k$-Extendable Graphs

Cites work

• 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 2104723 (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?)
• Bestimmung der Maximalzahl der Nachbargebiete auf nicht-orientierbaren Flächen
• Connectivity of \(k\)-extendable graphs with large \(k\).
• Generalization of matching extensions in graphs
• Graph Factors and Matching Extensions
• Graph minors. VIII: A Kuratowski theorem for general surfaces
• Matching extension and the genus of a graph
• On n-extendable graphs
• On the \(p\)-factor-criticality of the Klein bottle
• On the relationship between the genus and the cardinality of the maximum matchings of a graph
• Pairs of Hamiltonian circuits in 5-connected planar graphs
• Recent Progress in Matching Extension
• SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM
• The matching extendability of surfaces

Cited in

(8)

• The (\(n\), \(k\))-extendable graphs in surfaces
• scientific article; zbMATH DE number 5584098 (Why is no real title available?)
• Embeddings of 4-valent framed graphs into 2-surfaces
• On the restricted matching extension of graphs in surfaces
• Surface embeddability of graphs via homology
• Embedding grid graphs on surfaces
• Surface embeddings of the Klein and the Möbius–Kantor graphs
• Surface Embedding of Non-Bipartite $k$-Extendable Graphs

This page was built for publication: Surface embedding of \((n,k)\)-extendable graphs

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