Premium
Neighborhood unions and the cycle cover number of a graph
Author(s) -
Chen Guantao,
Gould Ronald J.,
Jacobson Michael S.,
Schelp Richard H.
Publication year - 1994
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.3190180703
Subject(s) - combinatorics , mathematics , graph , hamiltonian path , cover (algebra) , upper and lower bounds , discrete mathematics , mechanical engineering , mathematical analysis , engineering
For several years, the study of neighborhood unions of graphs has given rise to important structural consequences of graphs. In particular, neighborhood conditions that give rise to hamiltonian cycles have been considered in depth. In this paper we generalize these approaches to give a bound on the smallest number of cycles in G containing all the vertices of G . We show that if for all x , y ≅ V ( G ), | N ( x ) ∩ N ( y )| ≧ 2 n /5 + 1, then V ( G ) is coverable by at most two cycles. Several related results and extensions to t cycles are also given.