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$.