On the Geodomatic Number of a Graph

Abstract

A set $S$ of vertices of a graph $G$ is geodetic if every vertex in $V(G)\setminus S$ is contained in a shortest path between two vertices of $S$. The geodetic number $g(G)$ is the minimum cardinality of a geodetic set of $G$. The geodomatic number $d_g(G)$ of a graph $G$ is the maximum number of elements in a partition of $V(G)$ into geodetic sets.
In this paper, we determine $d_g(G)$ for some family of graphs, and we present different bounds on $d_g(G)$. In particular, we prove the following Nordhaus-Gaddum inequality, where $\overline{G}$ is the complement of the graph $G$. If $G$ is a graph of order $n\ge 2$, then $d_g(G)+d_g(\overline{G})\le n$ with equality if and only if $n=2$.