The connected vertex detour number of a graph
A. P. Santhakumaran, P. Titus · 2010
For a connected graph G of order p ≥ 2 and a vertex x of G, a set S ⊆ V(G) is an x-detour set of G if each vertex v ∈ V(G) lies on an x - y detour for some element y in S. The minimum cardinality of an x- detour set of G is defined as the x-detour number of G, denoted by dx(G). An x-detour set of cardinality dx(G) is called a dx-set of G. A connected x-detour set of G is an x-detour set S such that the subgraph G(S) induced by S is connected. The minimum cardinality of a connected x-detour set of G is defined as the connected x-detour number of G and is denoted by cdx(G). A connected x-detour set of cardinality cdx(G) is called a cdx- set of G. We determine bounds for the connected x-detour number and find the same for some special classes of graphs. If a, b and c are positive integers such that 3 ≤ a ≤ b+1 < c, then there exists a connected graph G with detour number dn(G) = a, dx(G) = b and cdx(G) = c for some vertex x in G. For positive integers R, D and n ≥ 3 with R < D ≤ 2R, there exists a connected graph G with radDG = R, diamDG = D and cdx(G) = n for some vertex x in G. Also, for each triple D, n and p of integers with 4 ≤ D ≤ p - 1 and 3 ≤ n ≤ p, there is a connected graph G of order p, detour diameter D and cdx(G) = n for some vertex x of G.