{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,4]],"date-time":"2024-05-04T00:30:15Z","timestamp":1714782615683},"reference-count":35,"publisher":"EDP Sciences","issue":"2","license":[{"start":{"date-parts":[[2024,5,3]],"date-time":"2024-05-03T00:00:00Z","timestamp":1714694400000},"content-version":"vor","delay-in-days":63,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2024,3,17]]},"published-print":{"date-parts":[[2024,3]]},"abstract":"A spanning subgraph F<\/jats:italic> of G<\/jats:italic> is called a path factor if every component of F<\/jats:italic> is a path of order at least 2. Let k<\/jats:italic> \u2265 2 be an integer. A P<\/jats:italic>\u2265k<\/jats:italic><\/jats:sub>-factor of G<\/jats:italic> means a path factor in which every component has at least k<\/jats:italic> vertices. A graph G<\/jats:italic> is called a P<\/jats:italic>\u2265k<\/jats:italic><\/jats:sub>-factor avoidable graph if for any e<\/jats:italic> \u2208 E<\/jats:italic>(G<\/jats:italic>), G<\/jats:italic> has a P<\/jats:italic>\u2265k<\/jats:italic><\/jats:sub>-factor avoiding e<\/jats:italic>. A graph G<\/jats:italic> is called a (P<\/jats:italic>\u2265k<\/jats:italic><\/jats:sub>, n<\/jats:italic>)-factor critical avoidable graph if for any W<\/jats:italic> \u2286 V<\/jats:italic> (G<\/jats:italic>) with |W|<\/jats:italic> = n<\/jats:italic>, G<\/jats:italic> \u2212 W<\/jats:italic> is a P<\/jats:italic>\u2265k<\/jats:italic><\/jats:sub>-factor avoidable graph. In other words, G<\/jats:italic> is (P<\/jats:italic>\u2265k<\/jats:italic><\/jats:sub>, n<\/jats:italic>)-factor critical avoidable if for any W<\/jats:italic> \u2286 V<\/jats:italic> (G<\/jats:italic>) with |W|<\/jats:italic> = n<\/jats:italic> and any e<\/jats:italic> \u2208 E<\/jats:italic>(G<\/jats:italic> \u2212 W<\/jats:italic> ), G<\/jats:italic> \u2212 W<\/jats:italic> \u2212 e<\/jats:italic> admits a P<\/jats:italic>\u2265k<\/jats:italic><\/jats:sub>-factor. In this article, we verify that (i) an (n<\/jats:italic> + r<\/jats:italic> + 2)-connected graph G<\/jats:italic> is (P<\/jats:italic>\u22652<\/jats:sub>, n<\/jats:italic>)-factor critical avoidable if I<\/jats:italic>(G<\/jats:italic>)>(n<\/jats:italic>+r<\/jats:italic>+2)\/(2(r<\/jats:italic>+2)) ; (ii) an (n<\/jats:italic> + r<\/jats:italic> + 2)-connected graph G<\/jats:italic> is (P<\/jats:italic>\u22653<\/jats:sub>, n<\/jats:italic>)-factor critical avoidable if t<\/jats:italic>(G<\/jats:italic>)>(n<\/jats:italic>+r<\/jats:italic>+2)\/(2(r<\/jats:italic>+2)) ; (iii) an (n<\/jats:italic> + r<\/jats:italic> + 2)-connected graph G<\/jats:italic> is (P<\/jats:italic>\u22653<\/jats:sub>, n<\/jats:italic>)-factor critical avoidable if I<\/jats:italic>(G<\/jats:italic>)>(n<\/jats:italic>+3(r<\/jats:italic>+2))\/(2(r<\/jats:italic>+2)) ; where n<\/jats:italic> and r<\/jats:italic> are two nonnegative integers.<\/jats:p>","DOI":"10.1051\/ro\/2024071","type":"journal-article","created":{"date-parts":[[2024,3,21]],"date-time":"2024-03-21T20:03:10Z","timestamp":1711051390000},"page":"2015-2027","source":"Crossref","is-referenced-by-count":0,"title":["Some existence theorems on path-factor critical avoidable graphs"],"prefix":"10.1051","volume":"58","author":[{"given":"Sizhong","family":"Zhou","sequence":"first","affiliation":[]},{"given":"Hongxia","family":"Liu","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2024,5,3]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Ando K., Egawa Y., Kaneko A., Kawarabayashi K. and Matsuda H., Path factors in claw-free graphs. Discrete Math. 243 (2002) 195\u2013200.","DOI":"10.1016\/S0012-365X(01)00214-X"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Bauer D., Katona G., Kratsch D. and Veldman H., Chordality and 2-factors in tough graphs. Discrete Appl. Math. 99 (2000) 323\u2013329.","DOI":"10.1016\/S0166-218X(99)00142-0"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Chv\u00e1tal V., Tough graphs and Hamiltonian circuits. Discrete Math. 5 (1973) 215\u2013228.","DOI":"10.1016\/0012-365X(73)90138-6"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Egawa Y. and Furuya M., The existence of a path-factor without small odd paths. Electron. J. Comb. 25 (2018) #P1.40.","DOI":"10.37236\/5817"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Gao W. and Wang W., New isolated toughness condition for fractional (g, f, n)-critical graphs. Colloquium Math. 147 (2017) 55\u201366.","DOI":"10.4064\/cm6713-8-2016"},{"key":"R6","unstructured":"Gao W., Liang L. and Chen Y., An isolated toughness condition for graphs to be fractional (k, m)-deleted graphs. Utilitas Math. 105 (2017) 303\u2013316."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Gao W., Guirao J. and Chen Y., A toughness condition for fractional (k, m)-deleted graphs revisited. Acta Math. Sinica-English Ser. 35 (2019) 1227\u20131237.","DOI":"10.1007\/s10114-019-8169-z"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Gao W., Wang W. and Chen Y., Tight bounds for the existence of path factors in network vulnerability parameter settings. Int. J. Intell. Syst. 36 (2021) 1133\u20131158.","DOI":"10.1002\/int.22335"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Kaneko A., 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\u2013218.","DOI":"10.1016\/S0095-8956(03)00027-3"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Kano M., Katona G.Y. and Kir\u00e1ly Z., Packing paths of length at least two. Discrete Math. 283 (2004) 129\u2013135.","DOI":"10.1016\/j.disc.2004.01.016"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Kano M., Lee C. and Suzuki K., Path and cycle factors of cubic bipartite graphs. Discuss. Math. Graph Theory 28 (2008) 551\u2013556.","DOI":"10.7151\/dmgt.1426"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Kano M., Lu H. and Yu Q., Component factors with large components in graphs. Appl. Math. Lett. 23 (2010) 385\u2013389.","DOI":"10.1016\/j.aml.2009.11.003"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Kelmans A., Packing 3-vertex paths in claw-free graphs and related topics. Discrete Appl. Math. 159 (2011) 112\u2013127.","DOI":"10.1016\/j.dam.2010.05.001"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Las Vergnas M., An extension of Tutte\u2019s 1-factor theorem. Discrete Math. 23 (1978) 241\u2013255.","DOI":"10.1016\/0012-365X(78)90006-7"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Liu G. and Zhang L., Toughness and the existence of fractional k-factors of graphs. Discrete Math. 308 (2008) 1741\u20131748.","DOI":"10.1016\/j.disc.2006.09.048"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"Wang S. and Zhang W., Degree conditions for the existence of a {P2, P5}-factor in a graph. RAIRO-Oper. Res. 57 (2023) 2231\u20132237.","DOI":"10.1051\/ro\/2023111"},{"key":"R17","unstructured":"Wang S. and Zhang W., Independence number, minimum degree and path-factors in graphs. Proc. Rom. Acad. Ser. A: Math. Phys. Tech. Sci. Inf. Sci. 23 (2022) 229\u2013234."},{"key":"R18","unstructured":"Wang S. and Zhang W., Some results on star-factor deleted graphs. Filomat 38 (2024) 1101\u20131107."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Wu J., Path-factor critical covered graphs and path-factor uniform graphs. RAIRO-Oper. Res. 56 (2022) 4317\u20134325.","DOI":"10.1051\/ro\/2022208"},{"key":"R20","unstructured":"Yang J., Ma Y. and Liu G., Fractional (g, f)-factors in graphs. Appl. Math. J. Chin. Univ. Ser. A 16 (2001) 385\u2013390."},{"key":"R21","doi-asserted-by":"crossref","unstructured":"Yuan Y. and Hao R., A neighborhood union condition for fractional ID-[a, b]-factor-critical graphs. Acta Math. Appl. Sin. Engl. Ser. 34 (2018) 775\u2013781.","DOI":"10.1007\/s10255-018-0786-2"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"Zhou S., A neighborhood union condition for fractional (a, b, k)-critical covered graphs. Discrete Appl. Math. 323 (2022) 343\u2013348.","DOI":"10.1016\/j.dam.2021.05.022"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"Zhou S., Remarks on restricted fractional (g, f)-factors in graphs. Discrete Appl. Math. (2022). DOI: 10.1016\/j.dam.2022.07.020.","DOI":"10.1016\/j.dam.2022.07.020"},{"key":"R24","unstructured":"Zhou S., Degree conditions and path factors with inclusion or exclusion properties. Bull. Math. Soc. Sci. Math. Roumanie 66 (2023) 3\u201314."},{"key":"R25","doi-asserted-by":"crossref","unstructured":"Zhou S., Path factors and neighborhoods of independent sets in graphs. Acta Math. Appl. Sin. Engl. Ser. 39 (2023) 232\u2013238.","DOI":"10.1007\/s10255-022-1096-2"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"Zhou S., Some results on path-factor critical avoidable graphs. Discuss. Math. Graph Theory 43 (2023) 233\u2013244.","DOI":"10.7151\/dmgt.2364"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"Zhou S. and Liu H., Two sufficient conditions for odd [1, b]-factors in graphs. Linear Algebra Appl. 661 (2023) 149\u2013162.","DOI":"10.1016\/j.laa.2022.12.018"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"Zhou S. and Zhang Y., Sufficient conditions for fractional [a, b]-deleted graphs. Indian J. Pure Appl. Math. (2024). DOI: 10.1007\/s13226-024-00564-w.","DOI":"10.1007\/s13226-024-00564-w"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"Zhou S., Bian Q. and Pan Q., Path factors in subgraphs. Discrete Appl. Math. 319 (2022) 183\u2013191.","DOI":"10.1016\/j.dam.2021.04.012"},{"key":"R30","unstructured":"Zhou S., Sun Z. and Yang F., A result on P\u22653-factor uniform graphs. Proc. Rom. Acad. Ser. A: Math. Phys. Tech. Sci. Inf. Sci. 23 (2022) 3\u20138."},{"key":"R31","doi-asserted-by":"crossref","unstructured":"Zhou S., Wu J. and Bian Q., On path-factor critical deleted (or covered) graphs. Aequationes Mathematicae 96 (2022) 795\u2013802.","DOI":"10.1007\/s00010-021-00852-4"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"Zhou S., Pan Q. and Xu L., Isolated toughness for fractional (2, b, k)-critical covered graphs. Proc. Rom. Acad. Ser. A: Math. Phys. Tech. Sci. Inf. Sci. 24 (2023) 11\u201318.","DOI":"10.59277\/PRA-SER.A.24.1.02"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"Zhou S., Sun Z. and Liu H., Some sufficient conditions for path-factor uniform graphs. Aequationes Mathematicae 97 (2023) 489\u2013500.","DOI":"10.1007\/s00010-023-00944-3"},{"key":"R34","doi-asserted-by":"crossref","first-page":"113927","DOI":"10.1016\/j.disc.2024.113927","volume":"347","author":"Zhou","year":"2024","journal-title":"Discrete Math."},{"key":"R35","doi-asserted-by":"crossref","first-page":"113940","DOI":"10.1016\/j.disc.2024.113940","volume":"347","author":"Zhou","year":"2024","journal-title":"Discrete Math."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024071\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,3]],"date-time":"2024-05-03T08:00:55Z","timestamp":1714723255000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024071"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3]]},"references-count":35,"journal-issue":{"issue":"2"},"alternative-id":["ro230771"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2024071","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"2804-7303","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3]]}}}