The \begin{document}$ \{K_2,C_n\} $\end{document}-factor of a graph is a spanning subgraph whose each component is either \begin{document}$ K_2 $\end{document} or \begin{document}$ C_n $\end{document}. In this paper, a sufficient condition with regard to tight toughness, isolated toughness and binding number bounds to guarantee the existence of the \begin{document}$ \{K_2,C_{2i+1}| i\geqslant 2 \} $\end{document}-factor for any graph is obtained, which answers a problem due to Gao and Wang (J Oper Res Soc China, 2021. https://doi.org/10.1007/s40305-021-00357-6).
Xia-Xia Guan, Tian-Long Ma, Chao Shi
. Tight Toughness, Isolated Toughness and Binding Number Bounds for the {K2, Cn}-Factors[J]. Journal of the Operations Research Society of China, 2025
, 13(2)
: 650
-659
.
DOI: 10.1007/s40305-023-00485-1
[1] Yu, Q.L., Liu, G.Z.: Graph Factors and Matching Extensions. Springer, Verlag (2009)
[2] Chvátal, V.: Tough graphs and Hamiltonian circuits. Discret. Math. 5, 215-228 (1973)
[3] Zhou, S.Z., Wu, J.C., Zhang, T.: The existence of \begin{document}$ P_{\geqslant 3} $\end{document}-factor covered graphs. Discuss. Math. Graph Theory 37(4), 1055-1065 (2017)
[4] Liu, G.Z., Zhang, L.J.: Toughness and the existence of fractional \begin{document}$ k $\end{document}-factors of graphs. Discret. Math. 308, 1741-1748 (2008)
[5] Gao, W., Chen, Y.J., Wang, Y.Q.: Network vulnerability parameter and results on two surfaces. Int. J. Intell. Syst. 36(8), 4392-4414 (2021)
[6] Yuan, Y., Hao, R.X.: Toughness condition for the existence of all fractional \begin{document}$ (a, b, k) $\end{document}-critical graphs. Discret. Math. 342, 2308-2314 (2019)
[7] Yang, J.B., Ma, Y.H., Liu, G.Z.: Fractional \begin{document}$ (g, f) $\end{document}-factors in graphs. Appl. Math. -J. Chin. Univ. Ser. A 16, 385-390 (2001)
[8] Kano, M., Lu, H.L., Yu, Q.L.: Component factors with large components in graphs. Appl. Math. Lett. 23, 385-389 (2010)
[9] Scheinerman, E., Ullman, D.: Fractional Graph Theory: A Rational Approach to the Theory of Graphs. John Wiley, New York (1997)
[10] Zhang, L.J., Liu, G.Z.: Fractional \begin{document}$ k $\end{document}-factor of graphs. J. Syst. Sci. Math. Sci. 21, 88-92 (2001)
[11] Gao, W., Wang, W.F.: Remarks on component factors. J. Oper. Res. Soc. China (2021). https://doi.org/10.1007/s40305-021-00357-6
[12] Woodall, D.: The binding number of a graph and its Anderson number. J. Comb. Theory Ser. B 15, 225-255 (1973)
[13] Anderson, I.: Perfect matchings of a graph. J. Comb. Theory Ser. B 10(3), 183-186 (1971)
[14] Katerinis, P., Woodall, D.R.: Binding numbers of graphs and the existence of \begin{document}$ k $\end{document}-factors. Q. J. Math. Oxf. II. Ser. 38(2), 221-228 (1987)
[15] Zhou, S.Z., Sun, Z.R.: Binding number conditions for \begin{document}$ P_{\geqslant 2} $\end{document}-factor and \begin{document}$ P_{\geqslant 3} $\end{document}-factor uniform graphs. Discret. Math. 343(3), 111715 (2020)
[16] Cornuejols, G., Pulleyblank, W.R.: Perfect triangle-free \begin{document}$ 2 $\end{document}-matchings. Math. Program. Stud. 13, 1-7 (1980)
