Article ID Journal Published Year Pages File Type
4650693 Discrete Mathematics 2008 6 Pages PDF
Abstract

The edge degree d(e)d(e) of the edge e=uve=uv is defined as the number of neighbours of e  , i.e., |N(u)∪N(v)|-2|N(u)∪N(v)|-2. Two edges are called remote if they are disjoint and there is no edge joining them. In this article, we prove that in a 2-connected graph G  , if d(e1)+d(e2)>|V(G)|-4d(e1)+d(e2)>|V(G)|-4 for any remote edges e1,e2e1,e2, then all longest cycles C in G   are dominating, i.e., G-V(C)G-V(C) is edgeless. This lower bound is best possible.As a corollary, it holds that if G   is a 2-connected triangle-free graph with σ2(G)>|V(G)|/2σ2(G)>|V(G)|/2, then all longest cycles are dominating.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,