Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650693 | Discrete Mathematics | 2008 | 6 Pages |
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
Kiyoshi Yoshimoto,