Research article

Component factors and binding number conditions in graphs

  • Received: 08 May 2021 Accepted: 27 August 2021 Published: 31 August 2021
  • MSC : 05C70

  • 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

    Related Papers:

  • 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
  • Reader Comments
  • © 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(1964) PDF downloads(60) Cited by(4)

Article outline

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog