### Analogies between the geodetic number and the Steiner number of some classes of graphs

#### Abstract

A set of vertices $S$ of a graph $G$ is a geodetic set of $G$ if

every vertex $v\not\in 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\ge 2$ and $H$ is a

non complete graph, then $g(G\odot H)\le s(G\odot H)$, which partially solve the open problem presented in [\emph{Discrete Mathematics} \textbf{280} (2004) 259--263] related to characterize families of graphs $G$ satisfying that $g(G)\le s(G)$.

every vertex $v\not\in 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\ge 2$ and $H$ is a

non complete graph, then $g(G\odot H)\le s(G\odot H)$, which partially solve the open problem presented in [\emph{Discrete Mathematics} \textbf{280} (2004) 259--263] related to characterize families of graphs $G$ satisfying that $g(G)\le s(G)$.

#### Full Text:

PDF### Refbacks

- There are currently no refbacks.