Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Open Access

# Two Sufficient Conditions for Component Factors in Graphs

###### Accepted: 21 Feb 2021
Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English

Let G be a graph. For a set ℋ of connected graphs, a spanning subgraph H of a graph G is called an ℋ-factor of G if each component of H is isomorphic to a member of ℋ. An ℋ-factor is also referred as a component factor. If Ge admits an ℋ-factor for any eE(G), then we say that G is an ℋ-factor deleted graph. Let k ≥ 2 be an integer. In this article, we verify that (i) a graph G admits a {K1,1, K1,2, . . ., K1,k, 𝒯 (2k + 1)}-factor if and only if its binding number bindbind(G)22k+1\left( G \right) \ge {2 \over {2k + 1}}; (ii) a graph G with δ (G) ≥ 2 is a {K1,1, K1,2, . . ., K1,k, 𝒯 (2k + 1)}-factor deleted graph if its binding number bind(G) ≥ bind(G)22k-1\left( G \right) \ge {2 \over {2k - 1}}.

#### MSC 2010

[1] J. Akiyama and M. Kano, Factors and Factorizations of Graphs, Lect. Note Math. 2031 (Springer, Berlin, Heidelberg, 2011). doi:10.1007/978-3-642-21919-1_110.1007/978-3-642-21919-1_1Search in Google Scholar

[2] A. Amahashi and M. Kano, On factors with given components, Discrete Math. 42 (1982) 1–6. doi:10.1016/0012-365X(82)90048-610.1016/0012-365X(82)90048-6Search in Google Scholar

[3] W. Gao, W. Wang and Y. Chen, Tight bounds for the existence of path factors in network vulnerability parameter settings, International Journal of Intelligent Systems 36 (2021) 1133–1158. doi:10.1002/int.2233510.1002/int.22335Search in Google Scholar

[4] M. Kano, H. Lu and Q. Yu, Component factors with large components in graphs, Appl. Math. Lett. 23 (2010) 385–389. doi:10.1016/j.aml.2009.11.00310.1016/j.aml.2009.11.003Search in Google Scholar

[5] M. Kano, H. Lu and Q. Yu, Fractional factors, component factors and isolated vertex conditions in graphs, Electron. J. Combin. 26 (2019) #P4.33. doi:10.37236/849810.37236/8498Search in Google Scholar

[6] M. Kano and A. Saito, Star-factors with large components, Discrete Math. 312 (2012) 2005–2008. doi:10.1016/j.disc.2012.03.01710.1016/j.disc.2012.03.017Search in Google Scholar

[7] M. Plummer and A. Saito, Toughness, binding number and restricted matching extension in a graph, Discrete Math. 340 (2017) 2665–2672. doi:10.1016/j.disc.2016.10.00310.1016/j.disc.2016.10.003Search in Google Scholar

[8] W.T. Tutte, The 1-factors of oriented graphs, Proc. Amer. Math. Soc. 4 (1953) 922–931. doi:10.2307/203183110.2307/2031831Search in Google Scholar

[9] S. Wang and W. Zhang, Research on fractional critical covered graphs, Probl. Inf. Transm. 56 (2020) 270–277. doi:10.1134/S003294602003004710.1134/S0032946020030047Search in Google Scholar

[10] J. Yu and G. Liu, Binding number and minimum degree conditions for graphs to have fractional factors, J. Shandong Univ. 39 (2004) 1–5.Search in Google Scholar

[11] Y. Zhang, G. Yan and M. Kano, Star-like factors with large components, J. Oper. Res. Soc. China 3 (2015) 81–88. doi:10.1007/s40305-014-0066-710.1007/s40305-014-0066-7Search in Google Scholar

[12] S. Zhou, Binding numbers and restricted fractional (g, f)-factors in graphs, Discrete Appl. Math., in press. doi:10.1016/j.dam.2020.10.01710.1016/j.dam.2020.10.017Search in Google Scholar

[13] S. Zhou, Remarks on path factors in graphs, RAIRO Oper. Res. 54 (2020) 1827–1834. doi:10.1051/ro/201911110.1051/ro/2019111Search in Google Scholar

[14] S. Zhou, Some results on path-factor critical avoidable graphs, Discuss. Math. Graph Theory, in press. doi:10.7151/dmgt.236410.7151/dmgt.2364Search in Google Scholar

[15] S. Zhou, H. Liu and Y. Xu, Binding numbers for fractional (a, b, k)-critical covered graphs, Proc. Rom. Acad. Ser. A Math. Phys. Tech. Sci. Inf. Sci. 21 (2020) 115–121.Search in Google Scholar

[16] S. Zhou and Z. Sun, Binding number conditions for P≥2-factor and P≥3-factor uniform graphs, Discrete Math. 343 (2020) #111715. doi:10.1016/j.disc.2019.11171510.1016/j.disc.2019.111715Search in Google Scholar

[17] S. Zhou and Z. Sun, Some existence theorems on path factors with given properties in graphs, Acta Math. Sin. (Engl. Ser.) 36 (2020) 917–928. doi:10.1007/s10114-020-9224-510.1007/s10114-020-9224-5Search in Google Scholar

• #### A Note About Monochromatic Components in Graphs of Large Minimum Degree

Recommended articles from Trend MD