×

Some existence theorems on path-factor critical avoidable graphs. (English) Zbl 1540.05149

Summary: A spanning subgraph \(F\) of \(G\) is called a path factor if every component of \(F\) is a path of order at least 2. Let \(k \geq 2\) be an integer. A \(P_{\geq k}\)-factor of \(G\) means a path factor in which every component has at least \(k\) vertices. A graph \(G\) is called a \(P_{\geq k}\)-factor avoidable graph if for any \(e \in E(G)\), \(G\) has a \(P_{\geq k}\)-factor avoiding \(e\). A graph \(G\) is called a \((P_{\geq k}, n)\)-factor critical avoidable graph if for any \(W \subseteq V(G)\) with \(|W| = n\), \(G - W\) is a \(P_{\geq k}\)-factor avoidable graph. In other words, \(G\) is \((P_{\geq k}, n)\)-factor critical avoidable if for any \(W \subseteq V(G)\) with \(|W| = n\) and any \(e \in E(G - W)\), \(G - W - e\) admits a \(P_{\geq k}\)-factor. In this article, we verify that (i) an \((n + r + 2)\)-connected graph \(G\) is \((P_{\geq 2}, n)\)-factor critical avoidable if \(I(G)> \frac{n+r+3}{2(r+2)}\); (ii) an \((n + r + 2)\)-connected graph \(G\) is \((P_{\geq 3}, n)\)-factor critical avoidable if \(t(G)>\frac{n+r+2}{2(r+2)}\); (iii) an \((n + r + 2)\)-connected graph \(G\) is \((P_{\geq 3}, n)\)-factor critical avoidable if \(I(G)>\frac{n+3(r+2)}{2(r+2)}\); where \(n\) and \(r\) are two nonnegative integers.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
90B10 Deterministic network models in operations research

References:

[1] K. Ando, Y. Egawa, A. Kaneko, K. Kawarabayashi and H. Matsuda, Path factors in claw-free graphs. Discrete Math. 243 (2002) 195-200. · Zbl 0992.05060
[2] D. Bauer, G. Katona, D. Kratsch and H. Veldman, Chordality and 2-factors in tough graphs. Discrete Appl. Math. 99 (2000) 323-329. · Zbl 0937.68094
[3] V. Chvátal, Tough graphs and Hamiltonian circuits. Discrete Math. 5 (1973) 215-228. · Zbl 0256.05122
[4] Y. Egawa and M. Furuya, The existence of a path-factor without small odd paths. Electron. J. Comb. 25 (2018) #P1.40. · Zbl 1391.05204
[5] W. Gao and W. Wang, New isolated toughness condition for fractional (𝑔, 𝑓, 𝑛)-critical graphs. Colloquium Math. 147 (2017) 55-66. · Zbl 1358.05228
[6] W. Gao, L. Liang and Y. Chen, An isolated toughness condition for graphs to be fractional (𝑘, 𝑚)-deleted graphs. Utilitas Math. 105 (2017) 303-316. · Zbl 1386.05153
[7] W. Gao, J. Guirao and Y. Chen, A toughness condition for fractional (𝑘, 𝑚)-deleted graphs revisited. Acta Math. Sinica-English Ser. 35 (2019) 1227-1237. · Zbl 1415.05149
[8] W. Gao, W. Wang and Y. Chen, Tight bounds for the existence of path factors in network vulnerability parameter settings. Int. J. Intell. Syst. 36 (2021) 1133-1158.
[9] 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 Ser. B 88 (2003) 195-218. · Zbl 1029.05125
[10] M. Kano, G.Y. Katona and Z. Király, Packing paths of length at least two. Discrete Math. 283 (2004) 129-135. · Zbl 1042.05084
[11] M. Kano, C. Lee and K. Suzuki, Path and cycle factors of cubic bipartite graphs. Discuss. Math. Graph Theory 28 (2008) 551-556. · Zbl 1173.05028
[12] M. Kano, H. Lu and Q. Yu, Component factors with large components in graphs. Appl. Math. Lett. 23 (2010) 385-389. · Zbl 1213.05158
[13] A. Kelmans, Packing 3-vertex paths in claw-free graphs and related topics. Discrete Appl. Math. 159 (2011) 112-127. · Zbl 1206.05058
[14] M. Las Vergnas, An extension of Tutte’s 1-factor theorem. Discrete Math. 23 (1978) 241-255. · Zbl 0404.05048
[15] G. Liu and L. Zhang, Toughness and the existence of fractional 𝑘-factors of graphs. Discrete Math. 308 (2008) 1741-1748. · Zbl 1136.05059
[16] S. Wang and W. Zhang, Degree conditions for the existence of a {𝑃 2 , 𝑃 5 }-factor in a graph. RAIRO-Oper. Res. 57 (2023) 2231-2237. · Zbl 1531.05210
[17] S. Wang and W. Zhang, Independence number, minimum degree and path-factors in graphs. Proc. Rom. Acad. Ser. A: Math. Phys. Tech. Sci. Inf. Sci. 23 (2022) 229-234.
[18] S. Wang and W. Zhang, Some results on star-factor deleted graphs. Filomat 38 (2024) 1101-1107.
[19] J. Wu, Path-factor critical covered graphs and path-factor uniform graphs. RAIRO-Oper. Res. 56 (2022) 4317-4325. · Zbl 1531.05211
[20] J. Yang, Y. Ma and G. Liu, Fractional (𝑔, 𝑓 )-factors in graphs. Appl. Math. J. Chin. Univ. Ser. A 16 (2001) 385-390. · Zbl 0991.05087
[21] Y. Yuan and R. Hao, A neighborhood union condition for fractional ID-[𝑎, 𝑏]-factor-critical graphs. Acta Math. Appl. Sin. Engl. Ser. 34 (2018) 775-781. · Zbl 1402.05119
[22] S. Zhou, A neighborhood union condition for fractional (𝑎, 𝑏, 𝑘)-critical covered graphs. Discrete Appl. Math. 323 (2022) 343-348. · Zbl 1502.05209
[23] S. Zhou, Remarks on restricted fractional (𝑔, 𝑓 )-factors in graphs. Discrete Appl. Math. (2022). DOI: 10.1016/j.dam.2022.07.020. · Zbl 1541.05125 · doi:10.1016/j.dam.2022.07.020
[24] S. Zhou, Degree conditions and path factors with inclusion or exclusion properties. Bull. Math. Soc. Sci. Math. Roumanie 66 (2023) 3-14. · Zbl 1538.05253
[25] S. Zhou, Path factors and neighborhoods of independent sets in graphs. Acta Math. Appl. Sin. Engl. Ser. 39 (2023) 232-238. · Zbl 1512.05343
[26] S. Zhou, Some results on path-factor critical avoidable graphs. Discuss. Math. Graph Theory 43 (2023) 233-244. · Zbl 1504.05236
[27] S. Zhou and H. Liu, Two sufficient conditions for odd [1, 𝑏]-factors in graphs. Linear Algebra Appl. 661 (2023) 149-162. · Zbl 1506.05179
[28] S. Zhou and Y. Zhang, Sufficient conditions for fractional [𝑎, 𝑏]-deleted graphs. Indian J. Pure Appl. Math. (2024). DOI: 10.1007/s13226-024-00564-w. · doi:10.1007/s13226-024-00564-w
[29] S. Zhou, Q. Bian and Q. Pan, Path factors in subgraphs. Discrete Appl. Math. 319 (2022) 183-191. · Zbl 1494.05102
[30] S. Zhou, Z. Sun and F. Yang, A result on 𝑃 ≥3 -factor uniform graphs. Proc. Rom. Acad. Ser. A: Math. Phys. Tech. Sci. Inf. Sci. 23 (2022) 3-8. · Zbl 1538.05151
[31] S. Zhou, J. Wu and Q. Bian, On path-factor critical deleted (or covered) graphs. Aequationes Mathematicae 96 (2022) 795-802. · Zbl 1520.05081
[32] S. Zhou, Q. Pan and L. Xu, Isolated toughness for fractional (2, 𝑏, 𝑘)-critical covered graphs. Proc. Rom. Acad. Ser. A: Math. Phys. Tech. Sci. Inf. Sci. 24 (2023) 11-18.
[33] S. Zhou, Z. Sun and H. Liu, Some sufficient conditions for path-factor uniform graphs. Aequationes Mathematicae 97 (2023) 489-500. · Zbl 1512.05344
[34] S. Zhou, Z. Sun and H. Liu, 𝒟-index and 𝒬-index for spanning trees with leaf degree at most 𝑘 in graphs. Discrete Math. 347 (2024) 113927. · Zbl 1535.05185
[35] S. Zhou, Y. Zhang and Z. Sun, The 𝐴𝛼-spectral radius for path-factors in graphs. Discrete Math. 347 (2024) 113940. · Zbl 1535.05186
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.