Premium
Sufficient conditions for the existence of a path‐factor which are related to odd components
Author(s) -
Egawa Yoshimi,
Furuya Michitaka,
Ozeki Kenta
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22253
Subject(s) - mathematics , combinatorics , path (computing) , factor (programming language) , graph , construct (python library) , existential quantification , discrete mathematics , computer science , programming language
In this article, we are concerned with sufficient conditions for the existence of a { P 2 , P 2 k + 1 } ‐factor. We prove that for k ≥ 3 , there existsε k > 0 such that if a graph G satisfies∑ 0 ≤ j ≤ k − 1c 2 j + 1( G − X ) ≤ ε k | X |for all X ⊆ V ( G ) , then G has a { P 2 , P 2 k + 1 } ‐factor, wherec 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 2 , P 2 k + 1 } ‐factor such that∑ 0 ≤ j ≤ k − 1c 2 j + 1( G − X ) ≤ 32 k + 141 72 k − 78| X |for all X ⊆ V ( G ) .