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

A. P. Santhakumaran
J. John

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.

Full text (pdf)

• 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
• Revised: 2009-06-17.
• Accepted: 2009-07-25.