Opuscula Math. 29, no. 4 (2009), 427-441

http://dx.doi.org/10.7494/OpMath.2009.29.4.427

Opuscula Mathematica

# The upper edge geodetic number and the forcing edge geodetic number of a graph

Abstract. An edge geodetic set of a connected graph \(G\) of order \(p \geq 2\) is a set \(S \subseteq V(G)\) such that every edge of \(G\) is contained in a geodesic joining some pair of vertices in \(S\). The edge geodetic number \(g_1(G)\) of \(G\) is the minimum cardinality of its edge geodetic sets and any edge geodetic set of cardinality \(g_1(G)\) is a minimum edge geodetic set of \(G\) or an edge geodetic basis of \(G\). An edge geodetic set \(S\) in a connected graph \(G\) is a minimal edge geodetic set if no proper subset of \(S\) is an edge geodetic set of \(G\). The upper edge geodetic number \(g_1^+(G)\) of \(G\) is the maximum cardinality of a minimal edge geodetic set of \(G\). The 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 \leq a \leq b\), there exists a connected graph \(G\) with \(g_1(G)=a\) and \(g_1^+(G)=b\). For an edge geodetic basis \(S\) of \(G\), a subset \(T \subseteq 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 \(f_1(S)\), is the cardinality of a minimum forcing subset of \(S\). The forcing edge geodetic number of \(G\), denoted by \(f_1(G)\), is \(f_1(G) = min\{f_1(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 \leq a \lt b\) and \(b \geq 2\), there exists a connected graph \(G\) such that \(f_1(G)=a\) and \(g_1(G)=b\).

Keywords: geodetic number, edge geodetic basis, edge geodetic number, upper edge geodetic number, forcing edge geodetic number.

Mathematics Subject Classification: 05C12.

- A. P. Santhakumaran
- St. Xavier’s College (Autonomous), Research Department of Mathematics, Palayamkottai - 627 002, India

- J. John
- Alagappa Chettiar Govt. College of Engineering & Technology, Department of Mathematics, Karaikudi - 630 004, India

- Received: 2008-09-19.
- Revised: 2009-06-17.
- Accepted: 2009-07-25.