Minimum size of n-factor-critical graphs and k-extendable graphs

DOI10.1007/S00373-011-1045-YMaRDI QIDQ1926044zbMATH OpenOpenAlexFDO

Authors Zan-Bo Zhang, Xiaoyan Zhang, Dingjun Lou, Xuelian Wen

Publication date 27 December 2012

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

minimum size\(k\)-extendable\(n\)-factor-critical

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We determine the minimum size of $n$-factor-critical graphs and that of $k$-extendable bipartite graphs, by considering Harary graphs and related graphs. Moreover, we determine the minimum size of $k$-extendable non-bipartite graphs for $k=1,2$, and pose a related conjecture for general $k$.

Recommendations

• Equivalence between extendability and factor-criticality
• Threshold functions for factor-critical graphs
• scientific article; zbMATH DE number 166077
• scientific article; zbMATH DE number 637274
• Minimally \(k\)-factor-critical graphs for some large \(k\)

Cites work

• scientific article; zbMATH DE number 4066957 (Why is no real title available?)
• scientific article; zbMATH DE number 1228444 (Why is no real title available?)
• scientific article; zbMATH DE number 1161241 (Why is no real title available?)
• scientific article; zbMATH DE number 238423 (Why is no real title available?)
• A Note on n-Critical Bipartite Graphs and Its Application
• Connectivity of \(k\)-extendable graphs with large \(k\).
• Equivalence between extendability and factor-criticality
• Extending matchings in graphs: A survey
• Graph Factors and Matching Extensions
• Graph theory with applications
• Independence number in n-extendable graphs
• New lower bound on the number of perfect matchings in fullerene graphs
• On \(k\)-factor-critical graphs
• On n-extendable graphs
• Recent Progress in Matching Extension
• THE MAXIMUM CONNECTIVITY OF A GRAPH

Cited in

(3)

• Perfect integer \(k\)-matching, \(k\)-factor-critical, and the spectral radius of graphs
• Minconvex Factors of Prescribed Size in Graphs
• Minimum \(k\)-critical bipartite graphs

This page was built for publication: Minimum size of \(n\)-factor-critical graphs and \(k\)-extendable graphs

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