ON CYCLES IN GRAPHS WITH SPECIFIED RADIUS AND DIAMETER

Abstract. Let G be a graph of radius r and diameter d with d ≤ 2r − 2. We show that G contains a cycle of length at least 4r−2d, i.e. for its circumference it holds c(G) ≥ 4r−2d. Moreover, for all positive integers r and d with r ≤ d ≤ 2r − 2 there exists a graph of radius r and diameter d with circumference 4r − 2d. For a connected graph G, the distance dG(u, v) or briefly d(u, v) between a pair of vertices u and v is the length of a shortest path joining them. The distance between a vertex u ∈ V (G) and a subgraph H of G will be denoted by d(u,H), i.e. d(u,H) = min{d(u, v); v ∈ V (H)}. The eccentricity eG(u) (briefly e(u)) of a vertex u of G is the distance of u to a vertex farthest from u in G, i.e. eG(u) = max{dG(u, v); v ∈ V (G)}. The radius radG of G is the minimum eccentricity among the vertices of G while the diameter diamG of G is the maximum eccentricity. The circumference of a graph G, denoted c(G), is the length of any longest cycle in G. A path P (a cycle C) in G is called geodesic if for any two vertices of P (of C) their distance in P (in C) equals their distance in G. A nontrivial connected graph with no cut-vertices is called a nonseparable graph. A block of a graph G is a maximal nonseparable subgraph of G. A connected unicyclic graph G with the cycle C is called a sun-graph (see [2]) if degG(u) ≤ 3 for u ∈ V (C) and degG(u) ≤ 2 for u ∈ V (G) \ V (C). A u − v path P in a sun-graph G is called a ra