The Detour Number of a Graph

Abstract

For vertices x and y in a graph G = (V, E), the detour distance D(x, y) is the length of a longest x - y path in G. An x - y path of length D(x, y) is called an x - y detour. The closed detour interval I_D[x, y] consists of x, y, and all vertices in some x - y detour of G. For S ⊆ V, I _D[S] is the union of the sets I_D[x, y] for all x, y ∈ S. A set S of vertices is a detour set if I_D[S] = V, and the minimum cardinality of a detour set is the detour number dn(G). A vertex that belongs to every minimum detour set is a detour vertex. It is shown that for every positive integer k, there exists a connected graph G containing a detour vertex of degree k. A detour set S, no proper subset of which is a detour set, is a minimal detour set. The upper detour number dn⁺(G) of a graph G is the maximum cardinality of a minimal detour set of G. It is shown that for every pair a, b of integers with 2 ≤ a ≤ b, there is a connected graph G with dn(G) = a and dn⁺(G) = b. A subset T of a minimum detour set S of G is a forcing subset for S if S is the unique minimum detour set containing T. The forcing detour number f_dn(S) of S is the minimum cardinality of a forcing subset for S. The forcing detour number f_dn(G) of G is min{f_dn(S)}, where the minimum is taken over all minimum detour sets S in G. It is shown that for each pair a, b of integers with 0 ≤ a ≤ b and b ≥ 2, there is a connected graph G with f_dn(G) = a and dn(G) = b.