Surface embedding of (n,k)-extendable graphs

DOI10.1016/J.DAM.2014.08.003zbMATH Open1303.05157arXiv1408.4046OpenAlexW2085774909MaRDI QIDQ477346FDOQ477346

David G. L. Wang, Hongliang Lu

Publication date: 3 December 2014

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

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)$.

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

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

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)

Cites Work

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

Cited In (8)

• Title not available (Why is that?)
• Surface embeddability of graphs via homology
• On the restricted matching extension of graphs in surfaces
• The (\(n\), \(k\))-extendable graphs in surfaces
• Embeddings of 4-valent framed graphs into 2-surfaces
• Surface Embedding of Non-Bipartite $k$-Extendable Graphs
• Embedding grid graphs on surfaces
• Surface embeddings of the Klein and the Möbius–Kantor 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)