Let $ G $ be a graph. For a set $ \mathcal{H} $ of connected graphs, an $ \mathcal{H} $-factor of a graph $ G $ is a spanning subgraph $ H $ of $ G $ such that every component of $ H $ is isomorphic to a member of $ \mathcal{H} $. A graph $ G $ is called an $ (\mathcal{H}, m) $-factor deleted graph if for every $ E'\subseteq E(G) $ with $ |E'| = m $, $ G-E' $ admits an $ \mathcal{H} $-factor. A graph $ G $ is called an $ (\mathcal{H}, n) $-factor critical graph if for every $ N\subseteq V(G) $ with $ |N| = n $, $ G-N $ admits an $ \mathcal{H} $-factor. Let $ m $, $ n $ and $ k $ be three nonnegative integers with $ k\geq2 $, and write $ \mathcal{F} = \{P_2, C_3, P_5, \mathcal{T}(3)\} $ and $ \mathcal{H} = \{K_{1, 1}, K_{1, 2}, \cdots, K_{1, k}, \mathcal{T}(2k+1)\} $, where $ \mathcal{T}(3) $ and $ \mathcal{T}(2k+1) $ are two special families of trees. In this article, we verify that (i) a $ (2m+1) $-connected graph $ G $ is an $ (\mathcal{F}, m) $-factor deleted graph if its binding number $ bind(G)\geq\frac{4m+2}{2m+3} $; (ii) an $ (n+2) $-connected graph $ G $ is an $ (\mathcal{F}, n) $-factor critical graph if its binding number $ bind(G)\geq\frac{2+n}{3} $; (iii) a $ (2m+1) $-connected graph $ G $ is an $ (\mathcal{H}, m) $-factor deleted graph if its binding number $ bind(G)\geq\frac{2}{2k-1} $; (iv) an $ (n+2) $-connected graph $ G $ is an $ (\mathcal{H}, n) $-factor critical graph if its binding number $ bind(G)\geq\frac{2+n}{2k+1} $.
Citation: Sizhong Zhou, Jiang Xu, Lan Xu. Component factors and binding number conditions in graphs[J]. AIMS Mathematics, 2021, 6(11): 12460-12470. doi: 10.3934/math.2021719
Let $ G $ be a graph. For a set $ \mathcal{H} $ of connected graphs, an $ \mathcal{H} $-factor of a graph $ G $ is a spanning subgraph $ H $ of $ G $ such that every component of $ H $ is isomorphic to a member of $ \mathcal{H} $. A graph $ G $ is called an $ (\mathcal{H}, m) $-factor deleted graph if for every $ E'\subseteq E(G) $ with $ |E'| = m $, $ G-E' $ admits an $ \mathcal{H} $-factor. A graph $ G $ is called an $ (\mathcal{H}, n) $-factor critical graph if for every $ N\subseteq V(G) $ with $ |N| = n $, $ G-N $ admits an $ \mathcal{H} $-factor. Let $ m $, $ n $ and $ k $ be three nonnegative integers with $ k\geq2 $, and write $ \mathcal{F} = \{P_2, C_3, P_5, \mathcal{T}(3)\} $ and $ \mathcal{H} = \{K_{1, 1}, K_{1, 2}, \cdots, K_{1, k}, \mathcal{T}(2k+1)\} $, where $ \mathcal{T}(3) $ and $ \mathcal{T}(2k+1) $ are two special families of trees. In this article, we verify that (i) a $ (2m+1) $-connected graph $ G $ is an $ (\mathcal{F}, m) $-factor deleted graph if its binding number $ bind(G)\geq\frac{4m+2}{2m+3} $; (ii) an $ (n+2) $-connected graph $ G $ is an $ (\mathcal{F}, n) $-factor critical graph if its binding number $ bind(G)\geq\frac{2+n}{3} $; (iii) a $ (2m+1) $-connected graph $ G $ is an $ (\mathcal{H}, m) $-factor deleted graph if its binding number $ bind(G)\geq\frac{2}{2k-1} $; (iv) an $ (n+2) $-connected graph $ G $ is an $ (\mathcal{H}, n) $-factor critical graph if its binding number $ bind(G)\geq\frac{2+n}{2k+1} $.
[1] | A. Amahashi, M. Kano, On factors with given components, Discrete Math., 42 (1982), 1–6. doi: 10.1016/0012-365X(82)90048-6 |
[2] | Y. Egawa, M. Kano, Z. Yan, Star-cycle factors of graphs, Discuss. Math. Graph T., 34 (2014), 193–198. doi: 10.7151/dmgt.1717 |
[3] | W. Gao, W. F. Wang, Y. J. Chen, Tight bounds for the existence of path factors in network vulnerability parameter settings, Int. J. Intell. Syst., 36 (2021), 1133–1158. doi: 10.1002/int.22335 |
[4] | M. Johnson, D. Paulusma, C. Wood, Path factors and parallel knock-out schemes of almost claw-free graphs, Discrete Math., 310 (2010), 1413–1423. doi: 10.1016/j.disc.2009.04.022 |
[5] | M. Kano, C. Lee, K. Suzuki, Path and cycle factors of cubic bipartite graphs, Discuss. Math. Graph T., 28 (2008), 551–556. doi: 10.7151/dmgt.1426 |
[6] | M. Kano, H. L. Lu, Q. L. Yu, Component factors with large components in graphs, Appl. Math. Lett., 23 (2010), 385–389. doi: 10.1016/j.aml.2009.11.003 |
[7] | M. Kano, H. L. Lu, Q. L. Yu, Fractional factors, component factors and isolated vertex conditions in graphs, Electron. J. Comb., 26 (2019), P4.33. doi: 10.37236/8498 |
[8] | M. Kano, A. Saito, Star-factors with large components, Discrete Math., 312 (2012), 2005–2008. doi: 10.1016/j.disc.2012.03.017 |
[9] | A. Kelmans, Packing 3-vertex paths in claw-free graphs and related topics, Discrete Appl. Math., 159 (2011), 112–127. doi: 10.1016/j.dam.2010.05.001 |
[10] | A. Klopp, E. Steffen, Fractional matchings, component-factors and edge-chromatic critical graphs, Graphs Comb., 37 (2021), 559–580. doi: 10.1007/s00373-020-02266-6 |
[11] | X. Y. Lv, A degree condition for fractional $(g, f, n)$-critical covered graphs, AIMS Math., 5 (2020), 872–878. doi: 10.3934/math.2020059 |
[12] | W. T. Tutte, The 1-factors of oriented graphs, P. Am. Math. Soc., 4 (1953), 922–931. |
[13] | S. Wang, W. Zhang, On $k$-orthogonal factorizations in networks, RAIRO-Oper. Res., 55 (2021), 969–977. doi: 10.1051/ro/2021037 |
[14] | S. Wang, W. Zhang, Research on fractional critical covered graphs, Probl. Inf. Transm., 56 (2020), 270–277. doi: 10.1134/S0032946020030047 |
[15] | D. R. Woodall, The binding number of a graph and its Anderson number, J. Comb. Theory B, 15 (1973), 225–255. |
[16] | J. Z. Wu, J. B. Yuan, W. Gao, Analysis of fractional factor system for data transmission in SDN, Appl. Math. Nonlinear Sci., 4 (2019), 191–196. doi: 10.2478/AMNS.2019.1.00025 |
[17] | Y. Yuan, R. X. Hao, A neighborhood union condition for fractional ID-$[a, b]$-factor-critical graphs, Acta Math. Appl. Sin.-Eng. Ser., 34 (2018), 775–781. doi: 10.1007/s10255-018-0786-2 |
[18] | Y. Yuan, R. X. Hao, Independence number, connectivity and all fractional $(a, b, k)$-critical graphs, Discuss. Math. Graph T., 39 (2019), 183–190. doi: 10.7151/dmgt.2075 |
[19] | S. Z. Zhou, A neighborhood union condition for fractional $(a, b, k)$-critical covered graphs, Discrete Appl. Math., DOI: 10.1016/j.dam.2021.05.022, In Press. |
[20] | S. Z. Zhou, Binding numbers and restricted fractional $(g, f)$-factors in graphs, Discrete Appl. Math., DOI: 10.1016/j.dam.2020.10.017, In Press. |
[21] | S. Z. Zhou, Remarks on path factors in graphs, RAIRO-Oper. Res., 54 (2020), 1827–1834. doi: 10.1051/ro/2019111 |
[22] | S. Z. Zhou, Some results on path-factor critical avoidable graphs, Discuss. Math. Graph T., DOI: 10.7151/dmgt.2364. |
[23] | S. Z. Zhou, Q. X. Bian, Q. R. Pan, Path factors in subgraphs, Discrete Appl. Math., DOI: 10.1016/j.dam.2021.04.012, In Press. |
[24] | S. Z. Zhou, Q. X. Bian, Z. Sun, Two sufficient conditions for component factors in graphs, Discuss. Math. Graph T., DOI: 10.7151/dmgt.2401. |
[25] | S. Z. Zhou, H. X. Liu, Y. Xu, A note on fractional ID-$[a, b]$-factor-critical covered graphs, Discrete Appl. Math., DOI: 10.1016/j.dam.2021.03.004, In Press. |
[26] | S. Z. Zhou, H. X. Liu, Y. Xu, Binding numbers for fractional $(a, b, k)$-critical covered graphs, P. Romanian Acad. A, 21 (2020), 115–121. |
[27] | S. Z. Zhou, Z. R. Sun, H. X. Liu, Isolated toughness and path-factor uniform graphs, RAIRO-Oper. Res., 55 (2021), 1279–1290. doi: 10.1051/ro/2021061 |
[28] | S. Z. Zhou, Z. R. Sun, Q. R. Pan, A sufficient condition for the existence of restricted fractional $(g, f)$-factors in graphs, Probl. Inf. Transm., 56 (2020), 332–344. doi: 10.1134/S0032946020040043 |
[29] | S. Z. Zhou, Y. Xu, Z. R. Sun, Degree conditions for fractional $(a, b, k)$-critical covered graphs, Inform. Process. Lett., 152 (2019), 105838. doi: 10.1016/j.ipl.2019.105838 |
[30] | S. Z. Zhou, F. Yang, L. Xu, Two sufficient conditions for the existence of path factors in graphs, Sci. Iran., 26 (2019), 3510–3514. |
[31] | S. Z. Zhou, T. Zhang, Z. R. Xu, Subgraphs with orthogonal factorizations in graphs, Discrete Appl. Math., 286 (2020), 29–34. doi: 10.1016/j.dam.2019.12.011 |