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:
PDFRefbacks
- There are currently no refbacks.