The Total Open Geodetic Number of a Graph

Abstract

For a connected graph $G$ of order $n\ge 2$, a set $S$ of vertices of $G$ is a geodetic set of $G$ if each vertex $v$ of $G$ lies on an $x$-$y$ geodesic for some elements $x$ and $y$ in $S$. The geodetic number $g(G)$ of $G$ is the minimum cardinality of a geodetic set of $G$. A geodetic set of cardinality $g(G)$ is called a $g$-set of $G$.

A set $S$ of vertices of a connected graph $G$ is an open geodetic set of $G$ if for each vertex $v$ in $G$, either $v$ is an extreme vertex of $G$ and $v\in S$; or $v$ is an internal vertex of an $x$-$y$ geodesic for some $x,y\in S$. An open geodetic set of minimum cardinality is a minimum open geodetic set, and this cardinality is the open geodetic number, $og(G)$.

A connected open geodetic set of $G$ is an open geodetic set $S$ such that the subgraph $⟨S⟩$ induced by $S$ is connected. The minimum cardinality of a connected open geodetic set of $G$ is the connected open geodetic number of $G$ and is denoted by $o{g}_c(G)$.

A total open geodetic set of a graph $G$ is an open geodetic set $S$ such that the subgraph $⟨S⟩$ induced by $S$ contains no isolated vertices. The minimum cardinality of a total open geodetic set of $G$ is the total open geodetic number of $G$ and is denoted by $o{g}_t(G)$. A total open geodetic set of cardinality $o{g}_t(G)$ is called an $o{g}_t$-set of $G$.

Certain general properties satisfied by total open geodetic sets are discussed. Graphs with total open geodetic number $2$ are characterized. The total open geodetic numbers of certain standard graphs are determined. It is proved that for positive integers $r$, $d$, and $k\ge 4$ with $r\le d\le 2r$, there exists a connected graph of radius $r$, diameter $d$, and total open geodetic number $k$. It is also proved that for the positive integers $a$, $b$, and $n$ with $4\le a\le b\le n$, there exists a connected graph $G$ of order $n$ such that $o{g}_t(G)=a$ and $o{g}_c(G)=b$.