We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Some existence theorems on path-factor critical avoidable graphs.
- Authors
Zhou, Sizhong; Liu, Hongxia
- Abstract
A spanning subgraph F of G is called a path factor if every component of F is a path of order at least 2. Let k ≥ 2 be an integer. A P≥k-factor of G means a path factor in which every component has at least k vertices. A graph G is called a P≥k-factor avoidable graph if for any e ∈ E(G), G has a P≥k-factor avoiding e. A graph G is called a (P≥k, n)-factor critical avoidable graph if for any W ⊆ V (G) with |W| = n, G − W is a P≥k-factor avoidable graph. In other words, G is (P≥k, n)-factor critical avoidable if for any W ⊆ V (G) with |W| = n and any e ∈ E(G − W), G − W − e admits a P≥k-factor. In this article, we verify that (i) an (n + r + 2)-connected graph G is (P≥2, n)-factor critical avoidable if I(G)>(n+r+2)/(2(r+2)) I (G) > n + r + 2 2 (r + 2) $I{(G)}>\frac{n+r+2}{2{(r+2)}}$ ; (ii) an (n + r + 2)-connected graph G is (P≥3, n)-factor critical avoidable if t(G)>(n+r+2)/(2(r+2)) t (G) > n + r + 2 2 (r + 2) $t{(G)}>\frac{n+r+2}{2{(r+2)}}$ ; (iii) an (n + r + 2)-connected graph G is (P≥3, n)-factor critical avoidable if I(G)>(n+3(r+2))/(2(r+2)) I (G) > n + 3 (r + 2) 2 (r + 2) $I{(G)}>\frac{n+3{(r+2)}}{2{(r+2)}}$ ; where n and r are two nonnegative integers.
- Subjects
EXISTENCE theorems; INTEGERS
- Publication
RAIRO: Operations Research (2804-7303), 2024, Vol 58, Issue 2, p2015
- ISSN
2804-7303
- Publication type
Article
- DOI
10.1051/ro/2024071