LONG DOMINATING CYCLES IN A KIND OF 2-CONNECTED GRAPHS

摘要

Let G be a connected graph of order of n, and NC2(G) denote min{|N(u) ∪ N(v)|| dist(u, v) = 2}, where dist(u, v) is the distance between u and v in G. A cycle C is called a dominating cycle if every component of GV(C) has order one. In this paper, we prove that if G is a 2-connected graph such that every longest cycle in G is a dominating cycle, then G contains a dominating cycle of length at least min{n, 2NC2(G)} unless G is the Petersen graph or belongs to a family of exceptional graphs.