Some results on path-factor critical avoidable graphs

Zhou, Sizhong 

Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 233-244

Résumé

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 P_≥ k={P_i:i≥ k}. Then a P_≥ k-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 P_≥ k-factor avoidable graph if for any e∈ E(G), G admits a P_≥ k-factor excluding e. A graph G is called a (P_≥ k,n)-factor critical avoidable graph if for any Q⊆ V(G) with |Q|=n, G-Q 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 (P_≥2,n)-factor critical avoidable graph if tough(G) gt; n+24; (ii) G is a (P_≥3,n)-factor critical avoidable graph if tough(G) gt;n+12; (iii) G is a (P_≥2,n)-factor critical avoidable graph if I(G) gt;n+23; (iv) G is a (P_≥3,n)-factor critical avoidable graph if I(G) gt;n+32. Furthermore, we claim that these conditions are sharp.

Détail

Keywords: graph, toughness, isolated toughness, $P_{\geq k}$-factor, $(P_{\geq k},n)$-factor critical avoidable graph