Free Access

Some Existence Theorems on Star Factors

Xiumin Wang

https://orcid.org/0009-0008-5566-2948

School of Mathematics and Statistics, Qinghai Normal University, Xining, Qinghai 810008, P. R. China

E-mail Address: wangxiumin1111@163.com

Search for more papers by this author

Fengyun Ren

https://orcid.org/0000-0002-5774-4399

School of Mathematics and Statistics, Qinghai Normal University, Xining, Qinghai 810008, P. R. China

E-mail Address: Renfengyun3@outlook.com

Corresponding author.

Search for more papers by this author

Dong He

https://orcid.org/0009-0007-0545-4676

School of Mathematics and Statistics, Qinghai Normal University, Xining, Qinghai 810008, P. R. China

E-mail Address: hedongac@126.com

Search for more papers by this author

, and

Ao Tan

https://orcid.org/0009-0002-2654-7269

School of Mathematics and Statistics, Qinghai Normal University, Xining, Qinghai 810008, P. R. China

E-mail Address: tanao1313@outlook.com

Search for more papers by this author

https://doi.org/10.1142/S0219265923500275Cited by:0 (Source: Crossref)

Abstract

The ${K_{1, 1}, K_{1, 2}, \dots, K_{1, k}, 𝒯 (2 k + 1)}$ -factor and ${K_{1, 2}, K_{1, 3}, K_{5}}$ -factor of a graph are a spanning subgraph whose each component is an element of ${K_{1, 1}, K_{1, 2}, \dots, K_{1, k}, 𝒯 (2 k + 1)}$ and ${K_{1, 2}, K_{1, 3}, K_{5}}$ , respectively, where $𝒯 (2 k + 1)$ is a special family of trees. In this paper, we obtain a sufficient condition in terms of tight toughness, isolated toughness and binding number bounds to guarantee the existence of a ${K_{1, 1}, K_{1, 2}, \dots, K_{1, k}, 𝒯 (2 k + 1)}$ -factor and ${K_{1, 2}, K_{1, 3}, K_{5}}$ -factor for any graph.

Keywords:

References

1. J. Akiyama and M. Kano , Factors and factorizations of graph, Springer-Verlag Berlin Heidelberg (Springer-Verlag, Berlin, 2011) p. xii+362. Google Scholar
2. J. A. Bondy and U. S. R. Murty , Graph Theory (GTM 244, Springer, 2008). Crossref, Google Scholar
3. P. Bonneville, E. Cheng and J. Renzi , Strong matching preclusion for the alternating group graphs, J. Interconnect. Netw. 12 (2011) 277–298. Link, Google Scholar
4. E. Cheng, S. Shah, V. Shah and D. E. Steffy , Strong matching preclusion for augmented cubes, Theor. Comput. Sci. 491 (2013) 71–77. Crossref, Web of Science, Google Scholar
5. V. Chvátal , Tough graphs and Hamiltonian circuits, Discrete Math. 5 (1973) 215–228. Crossref, Google Scholar
6. G. Dai , Remarks on component factors in graphs, RAIRO–Oper. Res. 56(2) (2022) 721–730. Crossref, Web of Science, Google Scholar
7. W. Gao and W. Wang , Remarks on component factors, J. Oper. Res. Soc. China 11 (2023) 657–666. Crossref, Web of Science, Google Scholar
8. X. Guan, T. Ma and C. Shi , Tight toughness, isolated toughness and binding number bounds for the ${K_{2}, C_{n}}$ -factors, J. Oper. Res. Soc. China (2023). Crossref, Google Scholar
9. M. Kano, H. Lu and Q. Yu , Component factors with large components in graphs, Appl. Math. Lett. 23 (2010) 385–389. Crossref, Web of Science, Google Scholar
10. M. Kano, H. Lu and Q. Yu, Fractional factors, component factors and isolated vertex conditions in graphs (2019) arXiv:1909.01009. Google Scholar
11. Y. Mao, Z. Wang, E. Cheng and C. Melekian , Strong matching preclusion number of graphs, Theor. Comput. Sci. 713 (2018) 11–20. Crossref, Web of Science, Google Scholar
12. J. H. Park and I. Ihm , Strong matching preclusion Theor. Comput. Sci. 412 (2011) 6409–6419. Crossref, Web of Science, Google Scholar
13. M. L. Vergnas , An extension of Tutte’s $1$ -factor theorem, Discrete Mathematics 23(3) (1978) 241–255. Crossref, Web of Science, Google Scholar
14. D. Woodall , The binding number of a graph and its Anderson number, J. Combin. Theory, Ser. B 15 (1973) 225–255. Crossref, Google Scholar
15. J. Yang, Y. Ma and G. Liu , Fractional $(g, f)$ -factors in graphs, Appl. Math. J. Chinese Univ., Ser. A 16 (2001) 385–390. Google Scholar
16. Q. Yu and G. Liu , Graph factors and matching extensions, Higher Education Press, Beijing (Springer-Verlag, Berlin, 2009), p. xii+353. Google Scholar
17. L. Zhang and G. Liu , Fractional $k$ -factor of graphs, J. Syst. Sci. Math. Sci. 21 (2001) 88–92. Google Scholar
18. S. Zhou , Some results about component factors in graphs, RAIRO Oper. Res. 53 (2019) 723–730. Crossref, Web of Science, Google Scholar
19. S. Zhou, Q. Bian and Z. Sun , Two sufficient conditions for component factors in graphs, Discussiones Mathematicae Graph Theory (2021). Web of Science, Google Scholar