Remarks on path factors in graphs

Zhou, Sizhong

RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 6, pp. 1827-1834.

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

A spanning subgraph of a graph is defined as a path factor of the graph if its component are paths. A P$$-factor means a path factor with each component having at least n vertices. A graph G is defined as a (P$$, m)-factor deleted graph if G–E′ has a P$$-factor for every E′ ⊆ E(G) with |E′| = m. A graph G is defined as a (P$$, k)-factor critical graph if after deleting any k vertices of G the remaining graph of G admits a P$$-factor. In this paper, we demonstrate that (i) a graph G is (P_≥3, m)-factor deleted if κ(G) ≥ 2m + 1 and bind(G) ≥  2/3 - $\frac{3}{2}-\frac{1}{4m+4}$; (ii) a graph G is (P_≥3, k)-factor critical if κ(G) ≥ k + 2 and bind(G) ≥ $\frac{5+k}{4}$.

[1] K. Ando, Y. Egawa, A. Kaneko, K. Kawarabayashi and H. Matsuda, Path factors in claw-free graphs, Discrete Math. 243 (2002) 195–200. | DOI | MR | Zbl

[2] H. Enomoto, M. Plummer and A. Saito, Neighborhood unions and factor critical graphs, Discrete Math. 205 (1999) 217–220. | DOI | MR | Zbl

[3] W. Gao and W. Wang, New isolated toughness condition for fractional $(g,f,n)$-critical graphs, Colloq. Math. 147 (2017) 55–66. | DOI | MR

[4] W. Gao, L. Liang, T. Xu and J. Zhou, Degree conditions for fractional $(g,f,n^{\text{'}},m)$-critical deleted graphs and fractional ID--critical deleted graphs and fractional ID-(-deleted graphs-critical deleted graphs and fractional ID-$(g , f , m)$-deleted graphs, Bull. Malaysian Math. Sci. Soc. 39 (2016) 315–330. | DOI | MR

[5] W. Gao, J. Guirao and H. Wu, Two tight independent set conditions for fractional $(g,f,m)$-deleted graphs systems, Qualitative Theory Dyn. Syst. 17 (2018) 231–243. | DOI | MR

[6] M. Johnson, D. Paulusma and C. Wood, Path factors and parallel knock-out schemes of almost claw-free graphs, Discrete Math. 310 (2010) 1413–1423. | DOI | MR | Zbl

[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. Comb. Theory Ser. B 88 (2003) 195–218. | DOI | MR | Zbl

[8] M. Kano, G.Y. Katona and Z. Király, Packing paths of length at least two, Discrete Math. 283 (2004) 129–135. | DOI | MR | Zbl

[9] K. Kawarabayashi, H. Matsuda, Y. Oda and K. Ota, Path factors in cubic graphs, J. Graph Theory 39 (2002) 188–193. | DOI | MR | Zbl

[10] A. Kelmans, Packing $3$-vertex paths in claw-free graphs and related topics, Discrete Appl. Math. 159 (2011) 112–127. | DOI | MR | Zbl

[11] R. Matsubara, H. Matsumura, M. Tsugaki and T. Yamashita, Degree sum conditions for path-factors with specified end vertices in bipartite graphs, Discrete Math. 340 (2017) 87–95. | DOI | MR

[12] Y. Nam, Binding numbers and connected factors, Graphs Comb. 26 (2010) 805–813. | DOI | MR | Zbl

[13] M. Plummer and A. Saito, Toughness, binding number and restricted matching extension in a graph, Discrete Math. 340 (2017) 2665–2672. | DOI | MR | Zbl

[14] A. Robertshaw and D. Woodall, Binding number conditions for matching extension, Discrete Math. 248 (2002) 169–179. | DOI | MR | Zbl

[15] Y. Yuan and R. Hao, Independence number, connectivity and all fractional $(a,b,k)$-critical graphs, Discuss. Math. Graph Theory 39 (2019) 183–190. | DOI | MR | Zbl

[16] S. Zhou, A sufficient condition for a graph to be an $(a,b,k)$-critical graph, Int. J. Comput. Math. 87 (2010) 2202–2211. | DOI | MR | Zbl

[17] S. Zhou, Binding numbers for fractional ID-$k$-factor-critical graphs, Acta Math. Sin. English Ser. 30 (2014) 181–186. | DOI | MR | Zbl

[18] S. Zhou, Some results about component factors in graphs, RAIRO: OR 53 (2019) 723–730. | DOI | Numdam | MR

[19] S. Zhou, Z. Sun and H. Ye, A toughness condition for fractional $(k,m)$-deleted graphs, Info. Process. Lett. 113 (2013) 255–259. | DOI | MR | Zbl

[20] S. Zhou, J. Wu and T. Zhang, The existence of $P_{\ge 3}$-factor covered graphs, Discuss. Math. Graph Theory 37 (2017) 1055–1065. | DOI | MR

[21] S. Zhou, L. Xu and Z. Xu, Remarks on fractional ID-$k$-factor-critical graphs, Acta Math. Appl. Sin. English Ser. 35 (2019) 458–464. | DOI | MR | Zbl

[22] S. Zhou, F. Yang and L. Xu, Two sufficient conditions for the existence of path factors in graphs, Sci. Iran. 26 (2019) 3510–3514.

[23] H. Zhang and S. Zhou, Characterizations for $P_{\ge 2}$-factor and $P_{\ge 3}$-factor covered graphs-factor and $-factor covered graphs, Discrete Math. 309 (2009) 2067–2076. | DOI | MR | Zbl