1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Some Results on Path-Factor Critical Avoidable Graphs

Published Online: 20 Oct 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 09 Jun 2020
Accepted: 03 Sep 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

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 Pk = {Pi : ik}. Then a Pk-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 Pk-factor avoidable graph if for any eE(G), G admits a Pk-factor excluding e. A graph G is called a (Pk, n)-factor critical avoidable graph if for any Q ⊆ V (G) with |Q| = n, GQ 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 (P2, n)-factor critical avoidable graph if tough(G)>n+24tough\left( G \right) > {{n + 2} \over 4}; (ii) G is a (P3, n)-factor critical avoidable graph if tough(G)>n+12tough\left( G \right) > {{n + 1} \over 2}; (iii) G is a (P2, n)-factor critical avoidable graph if I(G)>n+23I\left( G \right) > {{n + 2} \over 3}; (iv) G is a (P3, n)-factor critical avoidable graph if I(G)>n+32I\left( G \right) > {{n + 3} \over 2}. Furthermore, we claim that these conditions are sharp.

Keywords

MSC 2010

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

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

[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. doi:10.1002/jgt.2225310.1002/jgt.22253Search in Google Scholar

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

[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. doi:10.1007/s10114-019-8169-z10.1007/s10114-019-8169-zSearch in Google Scholar

[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.Search in Google Scholar

[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. doi:10.1016/S0095-8956(03)00027-310.1016/S0095-8956(03)00027-3Search in Google Scholar

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

[9] P. Katerinis, Toughness of graphs and the existence of factors, Discrete Math. 80 (1990) 81–92. doi:10.1016/0012-365X(90)90297-U10.1016/0012-365X(90)90297-USearch in Google Scholar

[10] 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.00110.1016/j.dam.2010.05.001Search in Google Scholar

[11] M. Las Vergnas, An extension of Tutte’s 1-factor theorem, Discrete Math. 23 (1978) 241–255. doi:10.1016/0012-365X(78)90006-710.1016/0012-365X(78)90006-7Search in Google Scholar

[12] S. Wang and W. Zhang, Research on fractional critical covered graphs, Probl. Inf. Transm. 56 (2020) 270–277. doi:10.1134/S003294602003004710.1134/S0032946020030047Search in Google Scholar

[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.Search in Google Scholar

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

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

[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.Search in Google Scholar

[17] S. Zhou and Z. Sun, Binding number conditions for P2-factor and P3-factor uniform graphs, Discrete Math. 343 (2020) 111715. doi:10.1016/j.disc.2019.11171510.1016/j.disc.2019.111715Search in Google Scholar

[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. doi:10.1007/s10114-020-9224-510.1007/s10114-020-9224-5Search in Google Scholar

[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) in press.10.1134/S0032946020040043Search in Google Scholar

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

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

[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. doi:10.24200/sci.2018.5151.112210.24200/sci.2018.5151.1122Search in Google Scholar

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo