Premium
A degree sum condition for longest cycles in 3‐connected graphs
Author(s) -
Yamashita Tomoki
Publication year - 2007
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.20210
Subject(s) - combinatorics , mathematics , degree (music) , vertex (graph theory) , graph , discrete mathematics , connectivity , physics , acoustics
For a graph G , we denote by d G ( x ) and κ( G ) the degree of a vertex x in G and the connectivity of G , respectively. In this article, we show that if G is a 3‐connected graph of order n such that d G ( x ) + d G ( y ) + d G ( z ) ≥ d for every independent set { x , y , z }, then G contains a cycle of length at least min{ d − κ( G ), n }. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 277–283, 2007