Paper Info
Title
Edge degrees and dominating cycles
Abstract
The edge degree d(e) of the edge e=uv is defined as the number of neighbours of e, i.e., |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)|-4 for any remote edges e1,e2, then all longest cycles C in G are dominating, i.e., G-V(C) is edgeless. This lower bound is best possible.
Year
DOI
Venue
2008
10.1016/j.disc.2007.05.003
Discrete Mathematics
Keywords
Field
DocType
Dominating cycle,Edge degree,Triangle-free graph,Longest cycle
Longest cycle,Graph,Discrete mathematics,Combinatorics,Disjoint sets,Bound graph,Upper and lower bounds,Corollary,Connectivity,Mathematics,Triangle-free graph
Journal
Volume
Issue
ISSN
308
12
0012-365X
Citations 
PageRank 
References 
0
0.34
2
Authors
1
Name
Order
Citations
PageRank
Kiyoshi Yoshimoto113322.65