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
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
|