Sufficient conditions for the existence of a path-factor which are related to odd components

2017/05/24 by Yoshimi Egawa, Egawa, Yoshimi, Michitaka Furuya +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1705.08592

18 pages, 1 figure

arxiv created 2017/05/24 · arxiv updated 2017/05/25

Abstract

In this paper, we are concerned with sufficient conditions for the existence of a \P₂,P_2k+1\-factor. We prove that for k≥ 3, there exists ε_k>0 such that if a graph G satisfies ∑_{0≤ j≤ k-1}c_2j+1(G-X)≤ ε_k|X| for all X⊆ V(G), then G has a \P₂,P_2k+1\-factor, where c_i(G-X) is the number of components C of G-X with |V(C)|=i. On the other hand, we construct infinitely many graphs G having no \P₂,P_2k+1\-factor such that ∑_{0≤ j≤ k-1}c_2j+1(G-X)≤ (32k+141)/(72k-78)|X| for all X⊆ V(G).

Related

• The existence of a path-factor without small odd paths
• Path-factors involving paths of order seven and nine
• Some sufficient conditions for graphs to have component factors
• Sufficient conditions for the existence of path-factors with given properties
• An Alternative Proof of the H-Factor Theorem