Remarks on path factors in graphs

School of Science, Jiangsu University of Science and Technology, Mengxi Road 2, 212003 Zhenjiang, Jiangsu, P.R. China

^* Corresponding author: zsz_cumt@163.com

Received: 17 May 2018
Accepted: 20 November 2019

Abstract

A spanning subgraph of a graph is defined as a path factor of the graph if its component are paths. A P_≥n-factor means a path factor with each component having at least n vertices. A graph G is defined as a (P_≥n, m)-factor deleted graph if G–E′ has a P_≥n-factor for every E′ ⊆ E(G) with |E′| = m. A graph G is defined as a (P_≥n, k)-factor critical graph if after deleting any k vertices of G the remaining graph of G admits a P_≥n-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) ≥ .