On the Detour Number and Geodetic Number of a Graph

Abstract

For vertices \(u\) and \(v\) in a connected graph \(G\) with vertex set \(V\), the distance \(d(u,v)\) is the length of a shortest \(u – v\) path in \(G\). A \(u – v\) path of length \(d(u,v)\) is called a \(u – v\) geodesic. The closed interval \(I[u,v]\) consists of \(u\), \(v\), and all vertices that lie in some \(u – v\) geodesic of \(G\); while for \(S \subseteq V\), \(I[S]\) is the union of closed intervals \(I[u,v]\) for all \(u,v \in S\). A set \(S\) of vertices is a geodetic set if \(I[S] = V\), and the minimum cardinality of a geodetic set is the geodetic number \(g(G)\). For vertices \(x\) and \(y\) in \(G\), 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 \subseteq V\), \(I_D[S]\) is the union of \(I_D[x,y]\) for all \(x,y \in 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)\). We study relationships that can exist between minimum detour sets and minimum geodetic sets in a graph. A graph \(F\) is a minimum detour subgraph if there exists a graph \(G\) containing \(F\) as an induced subgraph such that \(V(F)\) is a minimum detour set in \(G\). It is shown that \(K_3\) and \(P_3\) are minimum detour subgraphs. It is also shown that for every pair \(a,b \geq 2\) of integers, there exists a connected graph \(G\) with \(dn(G) = a\) and \(g(G) = b\).