Skip to main content

Advertisement

Springer Nature Link
Log in

Remarks on Component Factors

  • Published:
Journal of the Operations Research Society of China Aims and scope Submit manuscript

Abstract

In this remark, we first simply survey the important results on component factors in graphs. Then, we focus on the binding number condition of component factors in some special settings. The main contributions in this remark are two folded: (1) we reveal that the existence of some special component factors is equal to some specific binding number conditions; (2) the parameter conditions for a graph G with a \(P_{\tiny {\geqslant 3}}\)-factor are determined.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Explore related subjects

Discover the latest articles and news from researchers in related subjects, suggested using machine learning.

References

  1. Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, Berlin (2008)

    Book  MATH  Google Scholar 

  2. Chvátal, V.: Tough graphs and Hamiltonian circuits. Discrete Math. 5, 215–228 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  3. Yang, J., Ma, Y., Liu, G.: Fractional \((g, f)\)-factors in graphs. Appl. Math. J. Chin. Univ. Ser. A 16, 385–390 (2001)

    MATH  Google Scholar 

  4. Woodall, D.: The binding number of a graph and its Anderson number. J. Combin. Theory Ser. B 15, 225–255 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  5. Zhang, L., Liu, G.: Fractional \(k\)-factor of graphs. J. Syst. Sci. Math. Sci. 21(1), 88–92 (2001)

    MathSciNet  MATH  Google Scholar 

  6. Kaneko, A.: A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two. J. Combin. Theory Ser. B 88, 195–218 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  7. Wang, S., Zhang, W.: Research on fractional critical covered graphs. Probl. Inform. Transm. 56(3), 270–277 (2020)

    Article  MATH  Google Scholar 

  8. Zhou, S.: Binding numbers and restricted fractional \((g,f)\)-factors in graphs. Discrete Appl. Math. https://doi.org/10.1016/j.dam.2020.10.017 (2020)

  9. Zhou, S.: Some results on path-factor critical avoidable graphs, Discuss. Math. Graph Trans. https://doi.org/10.7151/dmgt.2364 (2020)

  10. Zhou, S., Sun, Z.: Binding number conditions for \(P_{\geqslant \!\!2}\)-factor and \(P_{\geqslant \!\!3}\)-factor uniform graphs. Discrete Math. 343(3), 111715 (2020)

  11. Zhou, S.: Remarks on path factors in graphs. RAIRO Oper. Res. 54(6), 1827–1834 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  12. Tutte, W.T.: The 1-factors of oriented graphs. Proc. Am. Math. Soc. 4, 922–931 (1953)

    Article  MathSciNet  MATH  Google Scholar 

  13. Cornuéjols, G., Pulleyblank, W.R.: Perfect triangle-free 2-matchings. In: Combinatorial Optimization, II (Proceedings of Conference University of East Anglia, Norwich, 1979), Mathematical Programming Studies, vol. 13, pp. 1–7 (1980)

  14. Egawa, Y., Furuya, M.: Sufficient conditions for the existence of pseudo 2-factors without isolated vertices and small odd cycles. Discrete Math. 341, 2276–2284 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  15. Las Vergnas, M.: An extension of Tutte’s 1-factor theorem. Discrete Math. 23, 241–255 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  16. Amahashi, A., Kano, M.: On factors with given components. Discrete Math. 42, 1–6 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  17. Zhou, S.: Some results about component factors in graphs. RAIRO Oper. Res. 53, 723–730 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  18. Berge, C., Las Vergnas, M.: On the existence of subgraphs with degree constraints. Indag. Math. (N.S.) 40, 165–176 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  19. Egawa, Y., Kano, M., Yan, Z.: Star-cycle factors of graphs. Discuss. Math. Graph Theory 34, 193–198 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  20. Kano, M., Lu, H., Yu, Q.: Component factors with large components in graphs. Appl. Math. Lett. 23, 385–389 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  21. Kano, M., Saito, A.: Star-factors with large components. Discrete Math. 312, 2005–2008 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  22. Zhang, Y., Yan, G., Kano, M.: Star-like factors with large components. J. Oper. Res. Soc. China 3, 81–88 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  23. Kano, M., Lu, H., Yu, Q.: Fractional factors, component factors and isolated vertex conditions in graphs. Electron. J. Combin. 26(4), No. 4.33 (2019)

  24. Cornuéjols, G., Hartvigsen, D.: An extension of matching theory. J. Combin. Theory Ser. B 40, 285–296 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  25. Gao, W., Wang, W., Chen, Y.: Tight bounds for the existence of path factors in network vulnerability parameter settings. Int. J. Intell. Syst. 36(3), 1133–1158 (2021)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Information Science and Technology, Yunnan Normal University, Kunming, 650500, Yunnan, China

    Wei Gao

  2. Department of Mathematics, Zhejiang Normal University, Jinhua, 321004, Zhejiang, China

    Wei-Fan Wang

Authors
  1. Wei Gao
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Wei-Fan Wang
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Wei Gao.

Additional information

The research is partially supported by the National Natural Science Foundation of China (No. 11761083).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gao, W., Wang, WF. Remarks on Component Factors. J. Oper. Res. Soc. China 11, 657–666 (2023). https://doi.org/10.1007/s40305-021-00357-6

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s40305-021-00357-6

Keywords

Mathematics Subject Classification