Analogies Between the Geodetic Number and the Steiner Number of some Classes of Graphs


Ismael G. Yero, Juan A. Rod\'riguez-Velázquez




A set of vertices $S$ of a graph $G$ is a geodetic set of $G$ if every vertex $v\notin S$ lies on a shortest path between two vertices of $S$. The minimum cardinality of a geodetic set of $G$ is the geodetic number of $G$ and it is denoted by $g(G)$. A Steiner set of $G$ is a set of vertices $W$ of $G$ such that every vertex of $G$ belongs to the set of vertices of a connected subgraph of minimum size containing the vertices of $W$. The minimum cardinality of a Steiner set of $G$ is the Steiner number of $G$ and it is denoted by $s(G)$. Let $G$ and $H$ be two graphs and let $n$ be the order of $G$. The corona product $G\odot H$ is defined as the graph obtained from $G$ and $H$ by taking one copy of $G$ and $n$ copies of $H$ and joining by an edge each vertex from the $i^{th}$-copy of $H$ to the $i_{th}$-vertex of $G$. We study the geodetic number and the Steiner number of corona product graphs. We show that if $G$ is a connected graph of order $n\geq 2$ and $H$ is a non complete graph, then $g(G\odot H)\leq s(G\odot H)$, which partially solve the open problem presented in [\emph{Discrete Mathematics} extbf{280} (2004) 259--263] related to characterize families of graphs $G$ satisfying that $g(G)\leq s(G)$.