Abstract

For a connected graph \textit{G} of order $n \geq 2$, a set $S \subseteq V(G)$ is a \textit{geodetic vertex cover} of \textit{G} if \textit{S} is both a geodetic set and a vertex cover of \textit{G}. The minimum cardinality of a geodetic vertex cover of \textit{G} is defined as the\textit{ geodetic vertex covering number} of \textit{G} and is denoted by $g_{\alpha}(G)$. Any geodetic vertex cover of cardinality $g_{\alpha}(G)$ is a $g_{\alpha} -$ set of \textit{G}. A \textit{connected geodetic vertex cover} of \textit{G} is a geodetic vertex cover \textit{S} such that the subgraph $G[S]$ induced by \textit{S} is connected. The minimum cardinality of a connected geodetic vertex cover of \textit{G} is the \textit{\textit{connected geodetic vertex covering number}} of \textit{G} and is denoted by $g_{\alpha c}(G)$. A connected geodetic vertex cover of cardinality $g_{\alpha c}(G)$ is called a $g_{\alpha c}$ - set of \textit{G}. Some general properties satisfied by connected geodetic vertex covering sets are studied. The connected geodetic vertex covering number of several classes of graphs are determined. Connected graphs of order \textit{n} with connected geodetic vertex covering number 2, 3, $\frac {n}{2}$ and \textit{n} are characterized. For any connected graph \textit{G} of order $n \geq 2$, the necessary and sufficient condition for $g_c(G) = g_{\alpha c}(G)$ is given.

Keywords and Phrases

Geodetic vertex cover, connected geodetic vertex cover, connected geodetic vertex covering number.

A.M.S. subject classification

05C12.

.....