RELATIVE LENGTH OF LONGEST PATHS AND CYCLES IN 2-CONNECTED GRAPHS

摘要

For a graph G, let p(G) and c(G) denote the number of vertices in a longest path and a longest cycle in G, respectively. In this paper, we prove that if G is a 2-connected graph G on n vertices with p(G) = p, where p ≥ 20, and if G has more than 1/2(p - 2)(n - 7) + 13 edges, then p(G) - c(G) ≤ 1, which implies that every longest cycle in G is a dominating cycle.