﻿Abstract
The Upper Connected Edge Geodetic Number of a Graph

A. P. Santhakumaran, J. John

For a non-trivial connected graph $G$, a set $S\subseteq V (G)$ is called an edge geodetic set of $G$ if 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 order of its edge geodetic sets and any edge geodetic set of order $g_1(G)$ is an edge geodetic basis. A connected edge geodetic set of $G$ is an edge geodetic set $S$ such that the subgraph $G[S]$ induced by $S$ is connected. The minimum cardinality of a connected edge geodetic set of $G$ is the connected edge geodetic number of $G$ and is denoted by $g_{1c}(G)$. A connected edge geodetic set of cardinality $g_{1c}(G)$ is called a $g_{1c^-}$ set of $G$ or connected edge geodetic basis of $G$. A connected edge geodetic set $S$ in a connected graph $G$ is called a minimal connected edge geodetic set if no proper subset of $S$ is a connected edge geodetic set of $G$. The upper connected edge geodetic number $g^+_{1c}(G)$ is the maximum cardinality of a minimal connected edge geodetic set of $G$. Graphs $G$ of order $p$ for which $g_{1c}(G)=g^+_{1c}=p$ are characterized. For positive integers $r,d$ and $n\geq d+1$ with $r\leq d \leq 2r$, there exists a connected graph of radius $r$, diameter $d$ and upper connected edge geodetic number $n$. It is shown for any positive integers $2\leq a<b\leq c$, there exists a connected graph $G$ such that $g_1(G)=a$,$g_{1c}(G)=b$ and $g^+_{1c}(G)=c$.