The vertex detour hull number of a graph
A. P. Santhakumaran, Ullas Chandran S.V. · Discussiones Mathematicae Graph Theory · 2012
For vertices x and y in a connected graph G, the detour distance D(x, y) is the length of a longest xy path in G.An xy path of length D(x, y) is an xy detour.The closed detour interval I D [x, y] consists of x, y, and all vertices lying on some xy detour of G; while for S ⊆ V (G), I D [S] = A.P. Santhakumaran and S.V. Ullas Chandran each pair of positive integers a, b with 2 ≤ a ≤ b + 1, there exist a connected graph G and a vertex x such that dh(G) = a and dh x (G) = b.It is proved that every two integers a and b with 1 ≤ a ≤ b, are realizable as the xdetour hull number and the x-detour number respectively.Also, it is shown that for integers a, b and n with 1 ≤ a ≤ nb and b ≥ 3, there exist a connected graph G of order n and a vertex x such that dh x (G) = a and the detour eccentricity of x, e D (x) = b.We determine bounds for dh x (G) and characterize graphs G which realize these bounds.