Geodesic
Some results on path-factor critical avoidable graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 233-244 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

A path factor is a spanning subgraph F of G such that every component of F is a path with at least two vertices. We write P_≥ k={P_i:i≥ k}. Then a P_≥ k-factor of G means a path factor in which every component admits at least k vertices, where k≥2 is an integer. A graph G is called a P_≥ k-factor avoidable graph if for any e∈ E(G), G admits a P_≥ k-factor excluding e. A graph G is called a (P_≥ k,n)-factor critical avoidable graph if for any Q⊆ V(G) with |Q|=n, G-Q is a P_≥ k-factor avoidable graph. Let G be an (n+2)-connected graph. In this paper, we demonstrate that (i) G is a (P_≥2,n)-factor critical avoidable graph if tough(G) gt; n+24; (ii) G is a (P_≥3,n)-factor critical avoidable graph if tough(G) gt;n+12; (iii) G is a (P_≥2,n)-factor critical avoidable graph if I(G) gt;n+23; (iv) G is a (P_≥3,n)-factor critical avoidable graph if I(G) gt;n+32. Furthermore, we claim that these conditions are sharp.
Keywords: graph, toughness, isolated toughness, $P_{\geq k}$-factor, $(P_{\geq k},n)$-factor critical avoidable graph 
@article{DMGT_2023_43_1_a15,
     author = {Zhou, Sizhong},
     title = {Some results on path-factor critical avoidable graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {233--244},
     year = {2023},
     volume = {43},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a15/}
}
TY  - JOUR
AU  - Zhou, Sizhong
TI  - Some results on path-factor critical avoidable graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 233
EP  - 244
VL  - 43
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a15/
LA  - en
ID  - DMGT_2023_43_1_a15
ER  - 
%0 Journal Article
%A Zhou, Sizhong
%T Some results on path-factor critical avoidable graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 233-244
%V 43
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a15/
%G en
%F DMGT_2023_43_1_a15
Zhou, Sizhong. Some results on path-factor critical avoidable graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 233-244. http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a15/

[1] S. Belcastro and M. Young, 1-factor covers of regular graphs, Discrete Appl. Math. 159 (2011) 281–287. https://doi.org/10.1016/j.dam.2010.12.003

[2] V. Chvátal, Tough graphs and Hamiltonian circuits, Discrete Math. 5 (1973) 215–228. https://doi.org/10.1016/0012-365X(73)90138-6

[3] Y. Egawa, M. Furuya and K. Ozeki, Sufficient conditions for the existence of a path-factor which are related to odd components, J. Graph Theory 89 (2018) 327–340. https://doi.org/10.1002/jgt.22253

[4] H. Enomoto, B. Jackson, P. Katerinis and A. Saito, Toughness and the existence of k-factors, J. Graph Theory 9 (1985) 87–95. https://doi.org/10.1002/jgt.3190090106

[5] W. Gao, J.L.C. Guirao and Y.J. Chen, A toughness condition for fractional (k,m)-deleted graphs revisited, Acta Math. Sin. (Engl. Ser.) 35 (2019) 1227–1237. https://doi.org/10.1007/s10114-019-8169-z

[6] W. Gao, L. Liang and Y. Chen, An isolated toughness condition for graphs to be fractional (k,m)-deleted graphs, Util. Math. 105 (2017) 303–316.

[7] 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. Combin. Theory Ser. B 88 (2003) 195–218. https://doi.org/10.1016/S0095-8956(03)00027-3

[8] M. Kano, H. Lu and Q. Yu, Component factors with large components in graphs, Appl. Math. Lett. 23 (2010) 385–389. https://doi.org/10.1016/j.aml.2009.11.003

[9] P. Katerinis, Toughness of graphs and the existence of factors, Discrete Math. 80 (1990) 81–92. https://doi.org/10.1016/0012-365X(90)90297-U

[10] A. Kelmans, Packing 3-vertex paths in claw-free graphs and related topics, Discrete Appl. Math. 159 (2011) 112–127. https://doi.org/10.1016/j.dam.2010.05.001

[11] 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

[12] S. Wang and W. Zhang, Research on fractional critical covered graphs, Probl. Inf. Transm. 56 (2020) 270–277. https://doi.org/10.1134/S0032946020030047

[13] J. Yang, Y. Ma and G. Liu, Fractional (g,f)-factors in graphs, Appl. Math. J. Chinese Univ. Ser. A 16 (2001) 385–390.

[14] S. Zhou, Remarks on orthogonal factorizations of digraphs, Int. J. Comput. Math. 91 (2014) 2109–2117. https://doi.org/10.1080/00207160.2014.881993

[15] S. Zhou, Remarks on path factors in graphs, RAIRO Oper. Res. 54 (2020) 1827–1834. https://doi.org/10.1051/ro/2019111

[16] S. Zhou, H. Liu and Y. Xu, Binding numbers for fractional (a,b,k)-critical covered graphs, Proc. Rom. Acad. Ser. A Math. Phys. Tech. Sci. Inf. Sci. 21 (2020) 115–121.

[17] S. Zhou and 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

[18] S. Zhou and Z. Sun, Some existence theorems on path factors with given properties in graphs, Acta Math. Sin. (Engl. Ser.) 36 (2020) 917–928. https://doi.org/10.1007/s10114-020-9224-5

[19] S. Zhou, Z. Sun and Q. Pan, A sufficient condition for the existence of restricted fractional (g,f)-factors in graphs, Probl. Inf. Transm. 56 (2020(4)) 35–49. https://doi.org/10.31857/S055529232004004X

[20] S. Zhou, Z. Sun and H. Ye, A toughness condition for fractional (k,m)-deleted graphs, Inform. Process. Lett. 113 (2013) 255–259. https://doi.org/10.1016/j.ipl.2013.01.021

[21] S. Zhou, Y. Xu and Z. Sun, Degree conditions for fractional (a,b,k)-critical covered graphs, Inform. Process. Lett. 152 (2019) 105838. https://doi.org/10.1016/j.ipl.2019.105838

[22] S. Zhou, F. Yang and L. Xu, Two sufficient conditions for the existence of path factors in graphs, Scientia Iranica 26 (2019) 3510–3514. https://doi.org/10.24200/sci.2018.5151.1122

[23] S. Zhou, T. Zhang and Z. Xu, Subgraphs with orthogonal factorizations in graphs, Discrete Appl. Math. 286 (2020) 29–34. https://doi.org/10.1016/j.dam.2019.12.011