no. 6
Remarks on path factors in graphs
RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 6, pp. 1827-1834

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 - 3 2-1 4m+4; (ii) a graph G is (P≥3, k)-factor critical if κ(G) ≥ k + 2 and bind(G) ≥ 5+k 4.

DOI : 10.1051/ro/2019111
Classification : 05C70, 05C38, 90B10
Keywords: Graph, path factor, binding number, connectivity 
@article{RO_2020__54_6_1827_0,
     author = {Zhou, Sizhong},
     title = {Remarks on path factors in graphs},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {1827--1834},
     year = {2020},
     publisher = {EDP Sciences},
     volume = {54},
     number = {6},
     doi = {10.1051/ro/2019111},
     mrnumber = {4150234},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2019111/}
}
TY  - JOUR
AU  - Zhou, Sizhong
TI  - Remarks on path factors in graphs
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2020
SP  - 1827
EP  - 1834
VL  - 54
IS  - 6
PB  - EDP Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2019111/
DO  - 10.1051/ro/2019111
LA  - en
ID  - RO_2020__54_6_1827_0
ER  - 
%0 Journal Article
%A Zhou, Sizhong
%T Remarks on path factors in graphs
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2020
%P 1827-1834
%V 54
%N 6
%I EDP Sciences
%U https://www.numdam.org/articles/10.1051/ro/2019111/
%R 10.1051/ro/2019111
%G en
%F RO_2020__54_6_1827_0
Zhou, Sizhong. Remarks on path factors in graphs. RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 6, pp. 1827-1834. doi: 10.1051/ro/2019111

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

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

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

[4] W. Gao, L. Liang, T. Xu and J. Zhou, Degree conditions for fractional ( g , f , n ' , 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. | MR | DOI

[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. | MR | DOI

[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. | MR | Zbl | DOI

[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. | MR | Zbl | DOI

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

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

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

[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. | MR | DOI

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

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

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

[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. | MR | Zbl | DOI

[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. | MR | Zbl | DOI

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

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

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

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

[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. | MR | Zbl | DOI

[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 ≥ 2 -factor and P ≥ 3 -factor covered graphs-factor and $-factor covered graphs, Discrete Math. 309 (2009) 2067–2076. | MR | Zbl | DOI

Cité par Sources :