The existence of path-factor uniform graphs with large connectivity

School of Science, Jiangsu University of Science and Technology, Zhenjiang, Jiangsu 212100, P.R. China

^* Corresponding author: zsz_cumt@163.com

Received: 27 December 2021
Accepted: 9 August 2022

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. Let k ≥ 2 be an integer. A P_≥k-factor of G means a path factor in which each component is a path with at least k vertices. A graph G is a P_≥k-factor covered graph if for any e ∈ E(G), G has a P_≥k-factor covering e. A graph G is called a P_≥k-factor uniform graph if for any e₁, e₂ ∈ E(G) with e₁ ≠ e₂, G has a P_≥k-factor covering e₁ and avoiding e₂. In other words, a graph G is called a P_≥k-factor uniform graph if for any e ∈ E(G), G − e is a P_≥k-factor covered graph. In this paper, we present two sufficient conditions for graphs to be P_≥3-factor uniform graphs depending on binding number and degree conditions. Furthermore, we show that two results are best possible in some sense.