Research article

Sufficient conditions for isolated tough graphs to have path-factors

  • Published: 13 May 2026
  • MSC : 05C38, 05C50, 05C70

  • Let $ G $ be a connected graph with $ n $ vertices, where $ n $ is a positive integer. The size of $ G $ is denoted by $ e(G) $. The isolated toughness of $ G $, denoted by $ I(G) $, is defined by

    $ I(G) = \min\left\{\frac{|S|}{i(G-S)}:S\subseteq V(G) \ \mbox{and} \ i(G-S)\geq2\right\} $

    or $ I(G) = +\infty $ if $ G $ is complete. A graph $ G $ is called isolated $ r $-tough if $ I(G)\geq r $. The distance signless Laplacian matrix $ \mathcal{Q}(G) $ of $ G $ is defined by $ \mathcal{Q}(G) = Tr(G)+\mathcal{D}(G) $, where $ \mathcal{D}(G) $ denotes the distance matrix of $ G $ and $ Tr(G) $ is the diagonal matrix of the vertex transmissions in $ G $. The largest eigenvalue of $ \mathcal{Q}(G) $, denoted by $ \eta(G) $, is called the distance signless Laplacian spectral radius of $ G $. A $ P_{\geq k} $-factor means a path factor with every component containing at least $ k $ vertices, where $ k $ is an integer with $ k\geq2 $. In this paper, we aim to establish two tight sufficient conditions based on $ e(G) $ and $ \eta(G) $ to guarantee that a graph $ G $ contains a $ P_{\geq2} $-factor. Let $ G $ be a connected isolated $ \frac{t}{2t+1} $-tough graph of order $ n $, where $ t\geq1 $ is an integer. Then the following two results hold.

    (ⅰ) If $ n\geq6t+2 $ and $ e(G)\geq e(K_t\vee(K_{n-3t-1}\cup(2t+1)K_1)) $, then $ G $ contains a $ P_{\geq2} $-factor unless $ G = K_t\vee(K_{n-3t-1}\cup(2t+1)K_1) $.

    (ⅱ) If $ n\geq9t+2 $ and $ \eta(G)\leq\eta(K_t\vee(K_{n-3t-1}\cup(2t+1)K_1)) $, then $ G $ contains a $ P_{\geq2} $-factor unless $ G = K_t\vee(K_{n-3t-1}\cup(2t+1)K_1) $.

    Citation: Quanru Pan, Sizhong Zhou. Sufficient conditions for isolated tough graphs to have path-factors[J]. AIMS Mathematics, 2026, 11(5): 13371-13383. doi: 10.3934/math.2026551

    Related Papers:

  • Let $ G $ be a connected graph with $ n $ vertices, where $ n $ is a positive integer. The size of $ G $ is denoted by $ e(G) $. The isolated toughness of $ G $, denoted by $ I(G) $, is defined by

    $ I(G) = \min\left\{\frac{|S|}{i(G-S)}:S\subseteq V(G) \ \mbox{and} \ i(G-S)\geq2\right\} $

    or $ I(G) = +\infty $ if $ G $ is complete. A graph $ G $ is called isolated $ r $-tough if $ I(G)\geq r $. The distance signless Laplacian matrix $ \mathcal{Q}(G) $ of $ G $ is defined by $ \mathcal{Q}(G) = Tr(G)+\mathcal{D}(G) $, where $ \mathcal{D}(G) $ denotes the distance matrix of $ G $ and $ Tr(G) $ is the diagonal matrix of the vertex transmissions in $ G $. The largest eigenvalue of $ \mathcal{Q}(G) $, denoted by $ \eta(G) $, is called the distance signless Laplacian spectral radius of $ G $. A $ P_{\geq k} $-factor means a path factor with every component containing at least $ k $ vertices, where $ k $ is an integer with $ k\geq2 $. In this paper, we aim to establish two tight sufficient conditions based on $ e(G) $ and $ \eta(G) $ to guarantee that a graph $ G $ contains a $ P_{\geq2} $-factor. Let $ G $ be a connected isolated $ \frac{t}{2t+1} $-tough graph of order $ n $, where $ t\geq1 $ is an integer. Then the following two results hold.

    (ⅰ) If $ n\geq6t+2 $ and $ e(G)\geq e(K_t\vee(K_{n-3t-1}\cup(2t+1)K_1)) $, then $ G $ contains a $ P_{\geq2} $-factor unless $ G = K_t\vee(K_{n-3t-1}\cup(2t+1)K_1) $.

    (ⅱ) If $ n\geq9t+2 $ and $ \eta(G)\leq\eta(K_t\vee(K_{n-3t-1}\cup(2t+1)K_1)) $, then $ G $ contains a $ P_{\geq2} $-factor unless $ G = K_t\vee(K_{n-3t-1}\cup(2t+1)K_1) $.



    加载中


    [1] R. Aharoni, A. Georgakopoulos, P. Sprüssel, Perfect matchings in $r$-partite $r$-graphs, Eur. J. Combin., 30 (2009), 39–42. https://doi.org/10.1016/j.ejc.2008.02.011 doi: 10.1016/j.ejc.2008.02.011
    [2] I. Anderson, Perfect matchings of a graph, J. Combin. Theory B, 10 (1971), 183–186. https://doi.org/10.1016/0095-8956(71)90041-4 doi: 10.1016/0095-8956(71)90041-4
    [3] G. Dai, The existence of path-factor covered graphs, Discuss. Math. Graph T., 43 (2023), 5–16. https://doi.org/10.7151/dmgt.2353 doi: 10.7151/dmgt.2353
    [4] H. Enomoto, Toughness and the existence of $k$-factors Ⅲ, Discrete Math., 189 (1998), 277–282. https://doi.org/10.1016/S0012-365X(98)00059-4 doi: 10.1016/S0012-365X(98)00059-4
    [5] Y. Hao, S. Li, Complete characterization of path-factor and path-factor covered graphs via $Q$-index and $D$-index, Linear Multilinear A., 72 (2024), 118–138. https://doi.org/10.1080/03081087.2022.2158166 doi: 10.1080/03081087.2022.2158166
    [6] A. Kaneko, A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two, J. Comb. Theory B, 88 (2003), 195–218. https://doi.org/10.1016/S0095-8956(03)00027-3 doi: 10.1016/S0095-8956(03)00027-3
    [7] M. Las Vergnas, An extension of Tutte's 1-factor theorem, Discrete Math., 23 (1978), 241–255. https://doi.org/10.1016/0012-365X(78)90006-7 doi: 10.1016/0012-365X(78)90006-7
    [8] S. Li, S. Miao, Characterizing $P_{\geq2}$-factor and $P_{\geq2}$-factor covered graphs with respect to the size or the spectral radius, Discrete Math., 344 (2021), 112588. https://doi.org/10.1016/j.disc.2021.112588 doi: 10.1016/j.disc.2021.112588
    [9] R. Liu, A. Fan, J. Shu, Spectral extremal problems on factors in tough graphs, and beyond, Discrete Math., 348 (2025), 114593. https://doi.org/10.1016/j.disc.2025.114593 doi: 10.1016/j.disc.2025.114593
    [10] H. Liu, X. Pan, Independence number and minimum degree for path-factor critical uniform graphs, Discrete Appl. Math., 359 (2024), 153–158. https://doi.org/10.1016/j.dam.2024.07.043 doi: 10.1016/j.dam.2024.07.043
    [11] S. Miao, S. Li, W. Wei, Matching extension and matching exclusion via the size or the spectral radius of graphs, Discrete Appl. Math., 347 (2024), 214–230. https://doi.org/10.1016/j.dam.2024.01.001 doi: 10.1016/j.dam.2024.01.001
    [12] H. Minc, Nonnegative matrices, New York: John Wiley & Sons, 1988.
    [13] T. Niessen, Neighborhood unions and regular factors, J. Graph Theor., 19 (1995), 45–64. https://doi.org/10.1002/jgt.3190190106 doi: 10.1002/jgt.3190190106
    [14] S. O, Spectral radius and matchings in graphs, Linear Algebra Appl., 614 (2021), 316–324. https://doi.org/10.1016/j.laa.2020.06.004 doi: 10.1016/j.laa.2020.06.004
    [15] W. T. Tutte, The factorization of linear graphs, J. London Math. Soc., 22 (1947), 107–111. https://doi.org/10.1112/jlms/s1-22.2.107 doi: 10.1112/jlms/s1-22.2.107
    [16] J. Wu, Characterizing spanning trees via the size or the spectral radius of graphs, Aequat. Math., 98 (2024), 1441–1455. https://doi.org/10.1007/s00010-024-01112-x doi: 10.1007/s00010-024-01112-x
    [17] J. Wu, Some results on the $k$-strong parity property in a graph, Comput. Appl. Math., 45 (2026), 138. https://doi.org/10.1007/s40314-025-03478-3 doi: 10.1007/s40314-025-03478-3
    [18] J. Wu, Sufficient conditions for a graph with minimum degree to have a component factor, P. Romanian Acad. A, 26 (2025), 1–8.
    [19] R. Xing, B. Zhou, J. Li, On the distance signless Laplacian spectral radius of graphs, Linear Multilinear A., 62 (2014), 1377–1387. https://doi.org/10.1080/03081087.2013.828720 doi: 10.1080/03081087.2013.828720
    [20] G. Liu, L. Zhang, Fractional $(g, f)$-factors in graphs, Appl. Math. Sci., 21 (2001), 541–545. https://doi.org/10.1016/S0252-9602(17)30443-5 doi: 10.1016/S0252-9602(17)30443-5
    [21] L. You, M. Yang, W. So, W. Xi, On the spectrum of an equitable quotient matrix and its application, Linear Algebra Appl., 577 (2019), 21–40. https://doi.org/10.1016/j.laa.2019.04.013 doi: 10.1016/j.laa.2019.04.013
    [22] H. Zhang, S. Zhou, Characterizations for $P_{\geq2}$-factor and $P_{\geq3}$-factor covered graphs, Discrete Math., 309 (2009), 2067–2076. https://doi.org/10.1016/j.disc.2008.04.022 doi: 10.1016/j.disc.2008.04.022
    [23] P. Zhang, Binding number conditions for path-factor uniform graphs, Bull. Malays. Math. Sci. Soc., 48 (2025), 124. https://doi.org/10.1007/s40840-025-01902-9 doi: 10.1007/s40840-025-01902-9
    [24] Y. Zhang, H. Lin, Perfect matching and distance spectral radius in graphs and bipartite graphs, Discrete Appl. Math., 304 (2021), 315–322. https://doi.org/10.1016/j.dam.2021.08.008 doi: 10.1016/j.dam.2021.08.008
    [25] S. Zhou, A result on spanning trees with bounded total excess, Discrete Appl. Math., 388 (2026), 130–135. https://doi.org/10.1016/j.dam.2026.03.025 doi: 10.1016/j.dam.2026.03.025
    [26] S. Zhou, Some spectral conditions for star-factors in bipartite graphs, Discrete Appl. Math., 369 (2025), 124–130. https://doi.org/10.1016/j.dam.2025.03.014 doi: 10.1016/j.dam.2025.03.014
    [27] S. Zhou, Spanning subgraphs and spectral radius in graphs, Aequat. Math., 100 (2026), 1. https://doi.org/10.1007/s00010-025-01255-5 doi: 10.1007/s00010-025-01255-5
    [28] S. Zhou, Q. Bian, Z. Sun, Spectral conditions for path-factors in isolated tough graphs, Discrete Appl. Math., 385 (2026), 228–236. https://doi.org/10.1016/j.dam.2026.02.015 doi: 10.1016/j.dam.2026.02.015
    [29] S. Zhou, Q. Bian, J. Wu, Sufficient conditions for even factors in graphs, Discrete Appl. Math., 386 (2026), 365–372. https://doi.org/10.1016/j.dam.2026.03.018 doi: 10.1016/j.dam.2026.03.018
    [30] S. Zhou, Z. Sun, Binding number conditions for $P_{\geq2}$-factor and $P_{\geq3}$-factor uniform graphs, Discrete Math., 343 (2020), 111715. https://doi.org/10.1016/j.disc.2019.111715 doi: 10.1016/j.disc.2019.111715
    [31] S. Zhou, Z. Sun, H. Liu, Distance signless Laplacian spectral radius for the existence of path-factors in graphs, Aequat. Math., 98 (2024), 727–737. https://doi.org/10.1007/s00010-024-01075-z doi: 10.1007/s00010-024-01075-z
    [32] S. Zhou, J. Wu, Spanning $k$-trees and distance spectral radius in graphs, J. Supercomput., 80 (2024), 23357–23366. https://doi.org/10.1007/s11227-024-06355-8 doi: 10.1007/s11227-024-06355-8
    [33] S. Zhou, Y. Zhang, Z. Sun, The $A_{\alpha}$-spectral radius for path-factors in graphs, Discrete Math., 347 (2024), 113940. https://doi.org/10.1016/j.disc.2024.113940 doi: 10.1016/j.disc.2024.113940
  • Reader Comments
  • © 2026 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(65) PDF downloads(7) Cited by(0)

Article outline

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog