Skip to main content
SpringerLink
Log in

Minimum Size of n-Factor-Critical Graphs and k-Extendable Graphs

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bondy J.A., Murty U.S.R.: Graph Theory with Applications. The Macmillan Press, London (1976)

    MATH  Google Scholar 

  2. Favaron O.: On k-factor-critical graphs. Discuss. Math. Graph Theory 16, 41–51 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  3. Harary F.: The maximum connetivity of a graph. Proc. Natl. Acad. Sci. USA 48, 1142–1164 (1962)

    Article  MATH  Google Scholar 

  4. Li Y., Nie Z.: A note on n-critical bipartite graphs and its application. In: Du, D., Hu, X., Pardalos, P.M. (eds) COCOA 2009. LNCS, vol. 5573, pp. 279–286. Springer, New York (2009)

    Google Scholar 

  5. Liu G., Yu Q.: On n-edge-deletable and n-critical graphs. Bull. Inst. Combin. Appl. 24, 65–72 (1998)

    MathSciNet  MATH  Google Scholar 

  6. Lou D., Yu Q.: Connectivity of k-extendable graphs with large k. Discrete Appl. Math. 136, 55–61 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  7. Maschlanka P., Volkmann L.: Independence number in n-extendable graphs. Discrete Math. 154, 167–178 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  8. Plummer M.D.: On n-extendable graphs. Discrete Math. 31, 201–210 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  9. Plummer M.D.: Matching extension in bipartite graphs. Congress. Numer. 54, 245–258 (1986)

    MathSciNet  Google Scholar 

  10. Plummer M.D.: Extending matchings in graphs: a survey. Discrete Math. 127, 277–292 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  11. Plummer M.D.: Extending matchings in graphs: an update. Congress. Numer. 116, 3–32 (1996)

    MathSciNet  MATH  Google Scholar 

  12. Plummer, M.D.: Recent progress in matching extension. In: Grötschel, M., Katona, G.O.H. (eds.) Building Bridges: Between Mathematics and Computer Science. Bolyai Society Mathematical Studies, vol. 19, pp. 427–454 (2008)

  13. Yu Q.: Characterizations of various matching extensions in graphs. Australas. J. Combin. 7, 55–64 (1993)

    MathSciNet  MATH  Google Scholar 

  14. Yu Q., Liu G.: Graph Factors and Matching Extensions. Higher Education Press, Beijing (2009)

    Book  MATH  Google Scholar 

  15. Zhang Z.-B., Wang T., Lou D.: Equivalence between extendibility and factor-criticality. Ars Combin. 85, 279–285 (2007)

    MathSciNet  MATH  Google Scholar 

  16. Zhang H., Zhang F.: New lower bound on the number of perfect matchings in fullerene graphs. J. Math. Chem. 30, 343–347 (2001)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Engineering, Guangdong Industry Technical College, Guangzhou, 510300, China

    Zan-Bo Zhang

  2. Department of Computer Science, Sun Yat-Sen University, Guangzhou, 510275, China

    Zan-Bo Zhang & Dingjun Lou

  3. School of Mathematical Science & Institute of Mathematics, Nanjing Normal University, Nanjing, 210097, China

    Xiaoyan Zhang

  4. Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, P.O. Box 217, 7500 AE, Enschede, The Netherlands

    Xiaoyan Zhang

  5. School of Economics and Management, South China Normal University, Guangzhou, 510006, China

    Xuelian Wen

Authors
  1. Zan-Bo Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xiaoyan Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dingjun Lou
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Xuelian Wen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xiaoyan Zhang.

Additional information

Research supported by NSFC (10801077), Natural Science Foundation of Guangdong Province (9451030007003340 and 9451009001002740), Natural Science Foundation of Jiangsu Higher Education Institutions of China (08KJB110008), and Science Research Foundation of Guangdong Industry Technical College.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zhang, ZB., Zhang, X., Lou, D. et al. Minimum Size of n-Factor-Critical Graphs and k-Extendable Graphs. Graphs and Combinatorics 28, 433–448 (2012). https://doi.org/10.1007/s00373-011-1045-y

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-011-1045-y

Keywords

Mathematics Subject Classification (2000)

Search

Navigation