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 - ; (ii) a graph G is (P≥3, k)-factor critical if κ(G) ≥ k + 2 and bind(G) ≥ .
Mots-clés : 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}, publisher = {EDP-Sciences}, volume = {54}, number = {6}, year = {2020}, doi = {10.1051/ro/2019111}, mrnumber = {4150234}, language = {en}, url = {http://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 - http://www.numdam.org/articles/10.1051/ro/2019111/ DO - 10.1051/ro/2019111 LA - en ID - RO_2020__54_6_1827_0 ER -
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. http://www.numdam.org/articles/10.1051/ro/2019111/
[1] Path factors in claw-free graphs, Discrete Math. 243 (2002) 195–200. | DOI | MR | Zbl
, , , and ,[2] Neighborhood unions and factor critical graphs, Discrete Math. 205 (1999) 217–220. | DOI | MR | Zbl
, and ,[3] New isolated toughness condition for fractional -critical graphs, Colloq. Math. 147 (2017) 55–66. | DOI | MR
and ,[4] Degree conditions for fractional -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
, , and ,[5] Two tight independent set conditions for fractional -deleted graphs systems, Qualitative Theory Dyn. Syst. 17 (2018) 231–243. | DOI | MR
, and ,[6] Path factors and parallel knock-out schemes of almost claw-free graphs, Discrete Math. 310 (2010) 1413–1423. | DOI | MR | Zbl
, and ,[7] 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] Packing paths of length at least two, Discrete Math. 283 (2004) 129–135. | DOI | MR | Zbl
, and ,[9] Path factors in cubic graphs, J. Graph Theory 39 (2002) 188–193. | DOI | MR | Zbl
, , and ,[10] Packing -vertex paths in claw-free graphs and related topics, Discrete Appl. Math. 159 (2011) 112–127. | DOI | MR | Zbl
,[11] Degree sum conditions for path-factors with specified end vertices in bipartite graphs, Discrete Math. 340 (2017) 87–95. | DOI | MR
, , and ,[12] Binding numbers and connected factors, Graphs Comb. 26 (2010) 805–813. | DOI | MR | Zbl
,[13] Toughness, binding number and restricted matching extension in a graph, Discrete Math. 340 (2017) 2665–2672. | DOI | MR | Zbl
and ,[14] Binding number conditions for matching extension, Discrete Math. 248 (2002) 169–179. | DOI | MR | Zbl
and ,[15] Independence number, connectivity and all fractional -critical graphs, Discuss. Math. Graph Theory 39 (2019) 183–190. | DOI | MR | Zbl
and ,[16] A sufficient condition for a graph to be an -critical graph, Int. J. Comput. Math. 87 (2010) 2202–2211. | DOI | MR | Zbl
,[17] Binding numbers for fractional ID--factor-critical graphs, Acta Math. Sin. English Ser. 30 (2014) 181–186. | DOI | MR | Zbl
,[18] Some results about component factors in graphs, RAIRO: OR 53 (2019) 723–730. | DOI | Numdam | MR
,[19] A toughness condition for fractional -deleted graphs, Info. Process. Lett. 113 (2013) 255–259. | DOI | MR | Zbl
, and ,[20] The existence of -factor covered graphs, Discuss. Math. Graph Theory 37 (2017) 1055–1065. | DOI | MR
, and ,[21] Remarks on fractional ID--factor-critical graphs, Acta Math. Appl. Sin. English Ser. 35 (2019) 458–464. | DOI | MR | Zbl
, and ,[22] Two sufficient conditions for the existence of path factors in graphs, Sci. Iran. 26 (2019) 3510–3514.
, and ,[23] Characterizations for -factor and -factor covered graphs-factor and $-factor covered graphs, Discrete Math. 309 (2009) 2067–2076. | DOI | MR | Zbl
and ,Cité par Sources :