Tight Toughness, Isolated Toughness and Binding Number Bounds for the {K2, Cn}-Factors

doi:10.1007/s40305-023-00485-1

Journal of the Operations Research Society of China ›› 2025, Vol. 13 ›› Issue (2): 650-659.doi: 10.1007/s40305-023-00485-1

Previous Articles Next Articles

Tight Toughness, Isolated Toughness and Binding Number Bounds for the {K₂, C_n}-Factors

Xia-Xia Guan, Tian-Long Ma, Chao Shi

School of Mathematical Sciences, Xiamen University, Xiamen 361005, Fujian, China

Received:2022-05-29 Online:2025-06-30 Published:2025-07-07
Contact: Tian-Long Ma E-mail:tianlongma@aliyun.com
Supported by:
The research was supported by the National Natural Science Foundation of China (No. 62006196).

Abstract

Abstract: 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).

Key words: Component factor, Toughness, Isolated toughness, Binding number

CLC Number:

05C42
05C38

Xia-Xia Guan, Tian-Long Ma, Chao Shi. Tight Toughness, Isolated Toughness and Binding Number Bounds for the {K₂, C_n}-Factors[J]. Journal of the Operations Research Society of China, 2025, 13(2): 650-659.

TrendMD

References

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

Tight Toughness, Isolated Toughness and Binding Number Bounds for the {K₂, C_n}-Factors

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics

Comments

[1]	Wei Gao, Wei-Fan Wang. Remarks on Component Factors [J]. Journal of the Operations Research Society of China, 2023, 11(3): 657-666.
[2]	Su-Fang Wang, Wei Zhang. Toughness for Fractional (2, b, k)-Critical Covered Graphs [J]. Journal of the Operations Research Society of China, 2023, 11(1): 197-206.