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

DOI10.1007/S00373-011-1045-YzbMATH Open1256.05199arXiv1707.07288OpenAlexW2114712088MaRDI QIDQ1926044FDOQ1926044

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)

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

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

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\)

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)

Cites Work

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

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)