Two Sufficient Conditions for Graphs to Admit Path Factors

Article type: Research Article

Authors: Zhou, Sizhong | Wu, Jiancheng^{; *}

Affiliations: School of Science, Jiangsu University of Science and Technology, Zhenjiang, Jiangsu 212100, China. [email protected], [email protected]

Correspondence: [*] Address for correspondence: School of Science, Jiangsu University of Science and Technology, Zhenjiang, Jiangsu 212100, China.

Abstract: Let 𝒜 be a set of connected graphs. Then a spanning subgraph A of G is called an 𝒜-factor if each component of A is isomorphic to some member of 𝒜. Especially, when every graph in 𝒜 is a path, A is a path factor. For a positive integer d ≥ 2, we write 𝒫≥d = {𝒫i|i ≥ d}. Then a 𝒫≥d-factor means a path factor in which every component admits at least d vertices. A graph G is called a (𝒫≥d,m)-factor deleted graph if G – E′ admits a 𝒫≥d-factor for any E′ ⊆ E(G) with |E′| = m. A graph G is called a (𝒫≥d, k)-factor critical graph if G – Q has a 𝒫≥d-factor for any Q ⊆ V (G) with |Q| = k. In this paper, we present two degree conditions for graphs to be (𝒫≥3,m)-factor deleted graphs and (𝒫≥3, k)-factor critical graphs. Furthermore, we show that the two results are best possible in some sense.

Keywords: graph, degree condition, 𝒫_≥3-factor, (𝒫_≥3,m)-factor deleted graph, (𝒫_≥3,k)-factor critical graph

Keywords: (2020) Mathematics Subject Classification: 05C70, 05C38

DOI: 10.3233/FI-242172

Journal: Fundamenta Informaticae, vol. 191, no. 1, pp. 67-77, 2024