Edge degrees and dominating cycles |
| |
Authors: | Kiyoshi Yoshimoto |
| |
Institution: | Department of Mathematics, College of Science and Technology, Nihon University, Tokyo 101-8308, Japan |
| |
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.As a corollary, it holds that if G is a 2-connected triangle-free graph with σ2(G)>|V(G)|/2, then all longest cycles are dominating. |
| |
Keywords: | Dominating cycle Edge degree Triangle-free graph Longest cycle |
本文献已被 ScienceDirect 等数据库收录! |
|