Premium
Two‐factors each component of which contains a specified vertex
Author(s) -
Egawa Yoshimi,
Enomoto Hikoe,
Faudree Ralph J.,
Li Hao,
Schiermeyer Ingo
Publication year - 2003
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.10113
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , order (exchange) , discrete mathematics , finance , economics
It is shown that if G is a graph of order n with minimum degree δ( G ), then for any set of k specified vertices { v 1 , v 2 ,…, v k } ⊂ V ( G ), there is a 2‐factor of G with precisely k cycles { C 1 , C 2 ,…, C k } such that v i ∈ V ( C i ) for (1 ≤ i ≤ k ) if $n = 3K,\delta(G)\ge\,{{7k-2}\over {3}}$ or 3 k + 1 ≤ n ≤ 4 k , $\delta (G)\,\ge\,{{2n+k-3}\over {3}}$ or 4 k ≤ n ≤ 6 k − 3,δ( G ) ≥ 3 k − 1 or n ≥ 6 k − 3, $\delta(G)\ge {{n}\over {2}}$ . Examples are described that indicate this result is sharp. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 188–198, 2003