The 2-edge geodetic number and graph operations
A. P. Santhakumaran, Ullas Chandran S.V. · Arabian Journal of Mathematics · 2012
For a connected graph G = (V, E) of order n ≥ 2, a set $${S\subseteq V}$$ is a 2-edge geodetic set of G if each edge $${e\in E - E(S)}$$ lies on a u-v geodesic with d(u, v) = 2 for some vertices u and v in S. The minimum cardinality of a 2-edge geodetic set in G is the 2-edge geodetic number of G, denoted by eg2(G). It is proved that for any connected graph G, β1(G) ≤ eg2(G), where β1(G) is the matching number of G. It is shown that every pair a, b of integers with 2 ≤ a ≤ b is realizable as the matching number and 2-edge geodetic number, respectively, of some connected graph. We determine bounds for the 2-edge geodetic number of Cartesian product of graphs. Also we determine the 2-edge geodetic number of certain classes of Cartesian product graphs. The 2-edge geodetic number of join of two graphs is obtained in terms of the 2-edge geodetic number of the factor graphs.