The upper edge geodetic number and the forcing edge geodetic number of a graph
A. P. Santhakumaran, J. John · Opuscula Mathematica · 2009
An edge geodetic set of a connected graph G of order p ≥ 2 is a set S ⊆ V (G) such that every edge of G is contained in a geodesic joining some pair of vertices in S. The edge geodetic number g1(G) of G is the minimum cardinality of its edge geodetic sets and anyThe upper edge geodetic number of certain classes of graphs are determined.It is shown that for every two integers a and b such that 2 ≤ a ≤ b, there exists a connected graph G with g1(G) = a and g + 1 (G) = b.For an edge geodetic basis S of G, a subset T ⊆ S is called a forcing subset for S if S is the unique edge geodetic basis containing T .A forcing subset for S of minimum cardinality is a minimum forcing subset of S. The forcing edge geodetic number of S, denoted by f1(S), is the cardinality of a minimum forcing subset of S. The forcing edge geodetic number of G, denoted by f1(G), is f1(G) = min{f1(S)}, where the minimum is taken over all edge geodetic bases S in G.Some general properties satisfied by this concept are studied.The forcing edge geodetic number of certain classes of graphs are determined.It is shown that for every pair a, b of integers with 0 ≤ a < b and b ≥ 2, there exists a connected graph G such that f1(G) = a and g1(G) = b.