Some Results on Path-Factor Critical Avoidable Graphs

Abstract

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 = {Pi : 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)>n+24tough\left( G \right) > {{n + 2} \over 4}; (ii) G is a (P≥3, n)-factor critical avoidable graph if tough(G)>n+12tough\left( G \right) > {{n + 1} \over 2}; (iii) G is a (P≥2, n)-factor critical avoidable graph if I(G)>n+23I\left( G \right) > {{n + 2} \over 3}; (iv) G is a (P≥3, n)-factor critical avoidable graph if I(G)>n+32I\left( G \right) > {{n + 3} \over 2}. Furthermore, we claim that these conditions are sharp.

Keywords

• graph
• toughness
• isolated toughness
• p≥k-factor
• (p≥k,n)-factor critical avoidable graph
• 05c70
• 05c38
• 90b10