The connected edge geodetic number of a graph

Abstract

For a non-trivial connected graph \(G\), a set \(S \subseteq V(G)\) is called an edge geodetic set of \(G\) if every edge of \(G\) is contained in a geodetic joining some pair of vertices in \(S\). The edge geodetic number \(g_1(G)\) of \(G\) is the minimum order of its edge geodetic sets and any edge geodetic set of order \(g_1(G)\) is an edge geodetic basis. A connected edge geodetic set of \(G\) is an edge geodetic set \(S\) such that the subgraph \(G[S]\) induced by \(S\) is connected. The minimum cardinality of a connected edge geodetic set of \(G\) is the connected edge geodetic number of \(G\) and is denoted by \(g_{1c}(G)\). A connected edge geodetic set of cardinality \(g_{1c}(G)\) is called a \(g_{1c}\) - set of \(G\) or a connected edge geodetic basis of \(G\). Some general properties satisfied by this concept are studied. The connected edge geodetic number of certain classes of graphs are determined. Connected graphs of order \(p\) with connected edge geodetic number \(p\) are characterized. Various necessary conditions for the connected edge geodetic number of a graph to be \(p - 1\) or \(p\) are given. It is shown that every pair \(k, p\) of integers with \(3 \leq k \leq p\) is realizable as the connected edge geodetic number and order of some connected graph. For positive integers \(r\) and \(n \geq d + 1\) with \(r \leq d \leq 2r\), there exists a connected graph of radius \(r\), diameter \(d\) and connected edge geodetic number \(n\). If \(p, d\) and \(n\) are integers such that \(2 \leq d \leq p - 1\) and \(d + 1 \leq n \leq p\), then there exists a connected graph \(G\) of order \(p\), diameter \(d\) and \(g_{1c}(G) = n\). Also if \(p, a\) and \(b\) are positive integers such that \(2 \leq a < b \leq p\), then there exists a connected graph \(G\) of order \(p, g_1(G) = a\) and \(g_{1c}(G) = b\).