# THE RESTRAINED STEINER NUMBER OF A GRAPH

J. John, M. S. Malchijah Raj

► To cite this version:

J. John, M. S. Malchijah Raj. THE RESTRAINED STEINER NUMBER OF A GRAPH. 2016. [hal-01389761]

HAL Id: hal-01389761

https://hal.science/hal-01389761v1

Preprint submitted on 29 Oct 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# THE RESTRAINED STEINER NUMBER OF A GRAPH

J. JOHN

Department of Mathematics

Government College of Engineering

Tirunelveli - 627 007, India.

e-mail: john@gcetly.ac.in

M. S. MALCHIJAH RAJ

Research Scholar

Research and Development Centre

Bharathiar University

Coimbatore – 641 046, India.

e-mail: malchijahraj@gmail.com

## Abstract

For a connected graph $G = (V, E)$ of order $p$, a set $W \subseteq V$ is called a Steiner set of $G$ if every vertex of $G$ is contained in a Steiner $W$-tree of $G$. The Steiner number $s(G)$ of $G$ is the minimum cardinality of its Steiner sets. A set $W$ of vertices of a graph $G$ is a *restrained Steiner set* if $W$ is a Steiner set, and if either $W = V$ or the subgraph $G[V - W]$ induced by $V - W$ has no isolated vertices. The minimum cardinality of a restrained Steiner set of $G$ is the *restrained Steiner number* of $G$, and is denoted by $s_r(G)$. The restrained Steiner number of certain classes of graphs are determined. Connected graphs of order $p$ with restrained Steiner number 2 are characterized. Various necessary conditions for the restrained Steiner number of a graph to be $p$ are given. It is shown that, for integers $a, b$ and $p$ with $4 \le a \le b \le p$, there exists a connected graph $G$ of order $p$ such that $s(G) = a$ and $s_r(G) = b$. It is also proved that for every pair of integers $a, b$ with $a \ge 3$ and $b \ge 3$, there exists a connected graph $G$ with $s_r(G) = a$ and $g_r(G) = b$.

**Keywords** : geodetic number, Steiner number, restrained geodetic number, restrained Steiner number.

**AMS Subject Classification:** 05C12

# 1 Introduction

By a graph $G = (V, E)$, we mean a finite undirected graph without loops or multiple edges. The order and size of $G$ are denoted by $p$ and $q$ respectively.
For every vertex $v \in V$, the *open neighborhood* $N(v)$ is the set $\{u \in V|uv \in E\}$ and the *closed neighborhood* of $v$ is the set $N[v] = N(v) \cup \{v\}$. The *degree* of a vertex $v \in V$ is $\deg_G(v) = \deg(v) = |N(v)|$. The *minimum* and *maximum degrees* of a graph $G$ are denoted by $\delta = \delta(G)$ and $\Delta = \Delta(G)$, respectively. The distance $d(u, v)$ between two vertices $u$ and $v$ in a connected graph $G$ is the length of a shortest $u-v$ path in $G$. An $u-v$ path of length $d(u, v)$ is called an $u-v$ geodesic. It is known that this distance is a metric on the vertex set $V(G)$. For basic graph theoretic terminology we refer to [9, 2]. For a vertex $v$ of $G$, the *eccentricity* $e(v)$ is the distance between $v$ and a vertex farthest from $v$. The minimum eccentricity among the vertices of $G$ is the radius, $\text{rad}G$ and the maximum eccentricity is its diameter, $\text{diam}G$ of $G$. Two vertices $x$ and $y$ are *antipodal* if $d(x, y) = \text{diam}G$. A vertex $v$ is an *extreme vertex* of a graph $G$ if the subgraph induced by its neighbors is complete. If $e = \{u, v\}$ is an edge of a graph $G$ with $d(u) = 1$ and $d(v) > 1$, then we call $e$ a pendant edge, $u$ a leaf or end vertex and $v$ a support. A *geodetic set* of $G$ is a set $S \subseteq V(G)$ such that every vertex of $G$ is contained in a geodesic joining some pair of vertices in $S$. The *geodetic number* $g(G)$ of $G$ is the minimum cardinality of its geodetic sets and any geodetic set of cardinality $g(G)$ is a *minimum geodetic set*. The geodetic number was introduced in [10] and further studied in [5, 11]. A set of vertices $S$ in a graph $G$ is a *restrained geodetic set* if $S$ is a geodetic set and the subgraph $G[V-S]$ induced by $V-S$ has no isolated vertices. The minimum cardinality of a restrained geodetic set, denoted by $g_r(G)$, is called the *restrained geodetic number* of $G$. A $g_r(G)$-set is a restrained geodetic set of cardinality $g_r(G)$. The restrained geodetic number of a graph was introduced in [1].

For a nonempty set $W$ of vertices in a connected graph $G$, the *Steiner distance* $d(W)$ of $W$ is the minimum size of a connected subgraph of $G$ containing $W$. Necessarily, each subgraph is a tree and is called a *Steiner tree* with respect to $W$ or a *Steiner W-tree*. $S(W)$ denotes the set of all vertices that lie on Steiner W-trees. A set $W \subseteq V(G)$ is called a *Steiner set* of $G$ if every vertex of $G$ lies on some Steiner W-tree or if $S(W) = V(G)$. A Steiner set of minimum cardinality is a *minimum Steiner set* or simply a $s$-set and this cardinality is the *Steiner number* $s(G)$ of $G$. The Steiner number of a graph was introduced in [6] and further studied in [11, 16, 18, 19, 20, 21].

The following theorems are used in the sequel.

**Theorem 1.1.** ([5, 6]) Each extreme vertex of a graph $G$ belongs to every geodetic set of $G$ as well as every Steiner set of $G$.

**Theorem 1.2.** ([6]) For the complete bipartite graph $G = K_{m,n}$,
$$s(G) = \begin{cases} 2 & \text{if } m = n = 1 \\ n & \text{if } n \ge 2, m = 1 \\ \min\{m, n\} & \text{if } m, n \ge 2 \end{cases}$$

**Theorem 1.3.** ([1]) Let $G$ be a connected graph of order $n \ge 3$. Then $g_r(G) = 2$ if and only if $g(G) = 2$ and $\text{diam}G \ge 3$ or $G = \overline{K}_2 \vee H$, where $\delta(H) \ge 1$.

**Theorem 1.4.** ([1]) For any tree $T$ different from star, $g_r(T) = |L(T)|$, where $L(T)$ is the set of all leaves of $T$. Moreover, $g_r(K_{1,r}) = r + 1$.

Throughout the following $G$ denotes a connected graph with at least two vertices.

## 2 The Restrained Steiner Number of a Graph

**Definition 2.1.** A set $W$ of vertices of a graph $G$ is a *restrained Steiner set* if $W$ is a Steiner set, and if either $W = V$ or the subgraph $G[V - W]$ induced by $V - W$ has no isolated vertices. The minimum cardinality of a restrained Steiner set of $G$ is the *restrained Steiner number* of $G$, and is denoted by $s_r(G)$. A restrained Steiner set of minimum cardinality is called the $s_r$-set of $G$.

<figure><img src="image_2.png" /><figcaption>Figure 2.1</figcaption></figure>
**Example 2.2.** For the graph $G$ given in Figure 2.1, it is clear that $W = \{v_1, v_3, v_5\}$ is a $s$-set of $G$ and so $s(G) = 3$, and $W_1 = \{v_1, v_3, v_4, v_5\}$ is a $s_r$-set so that $s_r(G) = 4$. Thus the Steiner number and the restrained Steiner number of a graph are different.

**Remark 2.3.** Every restrained Steiner set is a Steiner set, and the converse is not true. For the graph $G$ given in Figure 2.1, $W$ is a Steiner set of $G$, however it is not a restrained Steiner set of $G$. Also every restrained Steiner set of $G$ is a Steiner set of $G$.

Since every restrained Steiner set of $G$ is a Steiner set of $G$, the next result follows from Theorem 1.1.

**Theorem 2.4.** Each extreme vertex of a connected graph $G$ belongs to every restrained Steiner set of $G$.

**Corollary 2.5.** For the complete graph $K_p(p \ge 3)$, $s_r(K_p) = p$.

**Theorem 2.6.** For any connected graph $G$, $2 \le s(G) \le s_r(G) \le p$.

*Proof.* Any Steiner set needs at least two vertices and so $s(G) \ge 2$. Since every restrained Steiner set is a Steiner set, it follows that $s(G) \le s_r(G)$. Also, since $V(G)$ is a restrained Steiner set, it is clear that $s_r(G) \le p$. $\square$

**Remark 2.7.** The bounds in Theorem 2.6 are sharp. For any non trivial path $P_p(p \ge 2)$, the set of two end vertices is the unique Steiner set so that $s(P_p) = 2$. For the cycle $C_3$, $s(C_3) = s_r(C_3)$. For the complete graph $K_p$, $s_r(K_p) = p$. Also the inequalities are strict. For the graph $G$ given in Figure 2.1, $s(G) = 3$, $s_r(G) = 4$ and $p = 6$.

**Remark 2.8.** If $s(G) = p$ or $p-1$, then $s_r(G) = p$. The converse is not true. For the cycle $C_4$, $s(G) = 2 = p-2$ and $s_r(G) = 4 = p$.

**Theorem 2.9.** There is no graph of order $p$ with $s_r(G) = p-1$.

*Proof.* Since every restrained Steiner set of $G$ is a Steiner set of $G$ and the complement of each restrained Steiner set has cardinality different from one, we have $s_r(G) \ne p-1$. $\square$

**Theorem 2.10.** Let $G$ be a non trivial tree which is not a star. Then $s_r(G)$ is equal to the set of all end vertices of $G$.

*Proof.* Let $W$ be the set of all end vertices of $G$. Then $W$ is a restrained Steiner set of $G$. By Theorem 2.4, $s_r(G) \le |W|$. Since $G \ne K_{1,p-1}$, the subgraph $G[V-W]$ has no isolated vertices. Therefore $W$ is a restrained Steiner set of $G$ so that $s_r(G) = |W|$. $\square$
**Corollary 2.11.** For any tree $T$ with $p \ge 3$ vertices, $s_r(T) = p$ if and only if $T$ is a star.

**Corollary 2.12.** For any tree $T$ with $p \ge 4$ vertices, $s_r(T) = p - 2$ if and only if $T$ is a double star.

**Theorem 2.13.** For the cycle $G = C_p(p \ge 3)$, $s_r(G) = \begin{cases} p & \text{for } p \in \{3, 4, 5\} \\ 2 & \text{for } p \ge 6 \text{ and } p \text{ is even} \\ 3 & \text{for } p \ge 7 \text{ and } p \text{ is odd} \end{cases}$

*Proof.* It is clear that $s_r(C_p) = p$ for $p \in \{3, 4, 5\}$. Let $p \ge 6$. Let $p$ be even and $W = \{u, v\}$ be a set of antipodal vertices of $C_p$. Then $W$ is a Steiner set of $G$. Since the subgraph $G[V-W]$ has no isolated vertices, $W$ is a restrained Steiner set of $G$ so that $s_r(C_p) = 2$. Let $p$ be odd. It is clearly verified that no two element subset of $C_p$ is a Steiner set of $G$ and so $s_r(G) \ge 3$. For any vertex $u$, let $v$ and $w$ be the two antipodal vertices. Let $W_1 = \{u, v, w\}$. Then $W_1$ is a Steiner set of $G$. Since $p \ge 7$, the subgraph $G[V - W_1]$ has no isolated vertices. Then $W_1$ is a restrained Steiner set of $G$ so that $s_r(C_p) = 3$. $\square$

**Theorem 2.14.** For the complete bipartite graph $K_{m,n}(m, n \ge 2)$, $s_r(K_{m,n}) = m + n$.

*Proof.* Let $G = K_{m,n}(2 \le m \le n)$. Let $X$ and $Y$ be the bipartite sets of $G$, where $X = \{x_1, x_2, \dots, x_m\}$ and $Y = \{y_1, y_2, \dots, y_n\}$. Let $2 \le m < n$. By Theorem 1.2, $W = X$ is a $s$-set of $G$. Since the subgraph $G[V-W]$ has isolated vertices, $W$ is not a restrained Steiner set of $G$ and so $s_r(G) \ge m+1$. Let $W'$ be a restrained Steiner set of $G$ with $|W'| \ge m+1$. Then either $W' \subseteq Y$ or $W' \not\subseteq X \cup Y$. If $W' \subseteq Y$, then $W' = Y$ is the only Steiner set of $G$. Since the subgraph $G[V-W']$ has isolated vertices, $W'$ is not a restrained Steiner set of $G$, which is a contradiction. If $W' \not\subseteq X \cup Y$, then $<W'| >$ is connected. Then the Steiner $W'$-tree contains elements of $W'$ only. Therefore $W'$ is not a restrained Steiner set of $G$. Hence $W' = X \cup Y$. This implies $s_r(G) = m+n$. Similarly if $m=n$, we can prove that $s_r(G) = m+n$. $\square$

**Theorem 2.15.** For the wheel $W_p = K_1 + C_{p-1}$, $(p \ge 5)$, $s_r(W_p) = p - 3$.

*Proof.* Let $v$ be the vertex of $K_1$ and let $v_1, v_2, \dots, v_{p-1}, v_1$ be the cycle of $C_{p-1}$. For $p=5$, let $W = \{v_1, v_3\}$. Then $W$ is a Steiner set of $G$. Since the subgraph $G[V-W]$ has no isolated vertices, $W$ is a restrained Steiner set of $G$ so that $s_r(W_p) = 2 = p-3$. Let $p \ge 6$. Let $W$ be a Steiner set of $G$. If $v \in W$, then $<W'| >$ is connected. Then the Steiner $W$-tree contains elements of $W$ only. Therefore $v \notin W$. Hence $W \subseteq V(C_{p-1})$. Let
$W = \{v_1, v_3, v_4, \dots, v_{p-2}\}$. Then $W$ is a restrained Steiner set of $G$ and so $s_r(G) \le p-3$. We prove that $s_r(G) = p-3$. If not let $W'$ be a restrained Steiner set of $G$ with $|W'| \le p-4$. Then $v \notin W'$. Therefore there exists at least one $v_i \notin W'(1 \le i \le p-1)$. Then $v_i(1 \le i \le p-1)$ does not lie on any Steiner $W'$-tree of $G$ and so $W'$ is not a restrained Steiner set of $G$, which is a contradiction. Hence $s_r(G) = p-3$. $\square$

**Theorem 2.16.** Let $G$ be a connected graph of order $p \ge 2$. Then $s_r(G) = 2$ if and only if $g_r(G) = 2$.

*Proof.* Let $g_r(G) = 2$. By Theorem 1.3, $g(G) = 2$ and $\text{diam}G \ge 3$ or $G = \overline{K}_2 \vee H$, where $\delta(H) \ge 1$. Then it follows that $s_r(G) = 2$. Conversely let $s_r(G) = 2$. Let $W = \{u, v\}$ be a $s_r$-set of $G$. Since every Steiner $W$-tree is a $u-v$ geodesic and the subgraph $G[V-W]$ has no isolated vertices, $W$ is a restrained geodetic set of $G$ so that $g_r(G) = 2$. $\square$

**Corollary 2.17.** For the hyper cube $Q_n(n \ge 3)$, $s_r(Q_n) = 2$.

*Proof.* $Q_n$ has $2^n$ vertices, which may be labeled $(a_1a_2a_3\dots a_n)$, where each $a_i(1 \le i \le n)$ is either 0 or 1. It is easily seen that $\{(0, 0, 0, \dots, 0), (1, 1, 1, \dots, 1)\}$ is a $s_r(Q_n)$ set for $n \ge 3$. Hence $s_r(Q_n) = 2$. $\square$

**Theorem 2.18.** Let $G$ be a connected graph of order $p$ with exactly one vertex of degree $p-1$ which is not a cut vertex. Then $s_r(G) \le p-2$.

*Proof.* Let $x$ be the vertex of degree $p-1$ which is not a cut vertex of $G$. Since $\langle N(x) \rangle$ is non complete, there exist at least two non adjacent vertices say $y$ and $z$ such that $y$ and $z$ belong to $\langle N(x) \rangle$. Let $x_1$ be a vertex in $y-z$ geodesic. Then $W = V - \{x, z\}$ is a Steiner set of $G$. Since the subgraph $G[V-W]$ has no isolated vertices, $W$ is a restrained Steiner set of $G$ so that $s_r(G) \le p-2$. $\square$

<figure><img src="image_3.png" /><figcaption>$G$
Figure 2.2</figcaption></figure>
**Remark 2.19.** The bound in Theorem 2.18 is sharp. For the graph $G$ given in Figure 2.2, $W = \{v_1, v_3, v_4\}$ is a restrained Steiner set of $G$ so that $s_r(G) = 3 = p-2$.

**Theorem 2.20.** Let $G$ be a connected graph which contains a cut vertex of degree $p-1$. Then $s_r(G) = p$.

*Proof.* Let $x$ be a cut vertex of degree $p-1$. Let $W$ be a Steiner set of $G$. If $x \in W$, then $W = V$ is the only restrained Steiner set of $G$. If $x \notin W$, then $W = V - \{x\}$ is the only restrained Steiner set of $G$ and so $s_r(G) \ge p-1$. Since $s_r(G) \ne p-1$, $s_r(G) = p$. $\square$

<figure><img src="image_4.png" /><figcaption>Figure 2.3</figcaption></figure>

**Remark 2.21.** The converse of Theorem 2.20 need not be true. For the graph $G$ given in Figure 2.3 $s_r(G) = 7 = p$. But $G$ has no cut vertex of degree $p-1$.

**Theorem 2.22.** Let $G$ be the graph obtained from $K_{2,p-3}$, $p \ge 4$ by subdividing an edge once. Then $s_r(G) = p$.

*Proof.* Let $X = \{x_1, x_2\}$ and $Y = \{y_1, y_2, \dots, y_{p-3}\}$ be the bipartite sets of $K_{2,p-3}$. Without loss of generality we subdivide the edge $x_1y_1$ by the vertex $x$. If $W = \{x_1, x_2\}$, then the vertices $x$ and $y_1$ do not lie on any Steiner $W$-tree of $G$ and so $W$ is not a restrained Steiner set of $G$. If $W = \{y_1, y_2, \dots, y_{p-3}\}$, then the vertices $x$ and $x_1$ do not lie on any Steiner $W$-tree of $G$. If $W \subset Y$
or $W \subset X \cup Y$, then it is easily verified that $W$ is not a restrained Steiner set of $G$. If $W \subset Y \cup \{x\}$, then $W$ is not a restrained Steiner set of $G$. Similarly if $W \subset X \cup \{x\}$, then $W$ is not a restrained Steiner set of $G$. Therefore $W \subset X \cup Y \cup \{x\}$. If $W \subsetneq X \cup Y \cup \{x\}$ such that $W$ contains at least one vertex in $X$ and $W$ contains at least one vertex in $Y$, then the Steiner $W$-tree contains the vertices adjacent to $x$ and the elements of $W$ only and hence $S(W) \neq V$. Then it follows that $W$ is not a restrained Steiner set of $G$. Therefore $W = X \cup Y \cup \{x\}$. Hence $s_r(G) = p$. $\square$

If $G$ is $C_4$ or $C_5$ or $K_{m,n}$ or a connected graph which contains a cut vertex of degree $p-1$ or the graph obtained from $K_{2,p-3}, p \ge 4$ by subdividing an edge once or the graph given in Figure 2.3, then $s_r(G) = p$. So we have the following open problem.

**Problem 2.23.** Characterize graphs for which $s_r(G) = p$.

**Theorem 2.24.** For positive integers $r, d$ and $l \ge 2$ with $r \le d \le 2r$, there exists a connected graph $G$ with $\text{rad}G = r$, $\text{diam}G = d$ and $s_r(G) = l$.

*Proof.* When $r=1$, then $d=1$ or $d=2$. If $d=1$, then $G = K_l$ has the desired properties. If $d=2$, then $G = K_{1,l-1}$ has the desired properties. If $r=d=2$, then $G = K_{2,l-2}$ has the desired properties. Now, let $r \ge 3$. Construct a graph $G$ with the desired properties as follows:

**Case 1.** $r=d$. Let $C_{2r}: u_1, u_2, \dots, u_{2r}, u_1$ be a cycle of order $2r$. Let $G$ be the graph obtained from $C_{2r}$ by adding $l-2$ new vertices $x_1, x_2, \dots, x_{l-2}$ and joining each $x_i$ ($1 \le i \le l-2$) with the vertices $u_1$ and $u_2$ of $C_{2r}$. The graph $G$ is shown in Figure 2.4.

<figure><img src="image_5.png" /></figure>
<caption>Figure 2.4

$G$</caption>

It is easily verified that the eccentricity of each vertex of $G$ is $r$ so that $\mathrm{rad}G = \mathrm{diam}G = r$. Let $X = \{x_1, x_2, \dots, x_{l-2}\}$ be the set of all extreme vertices of $G$ with $|X| = l-2$. By Theorem 2.4, $X$ is a subset of every restrained Steiner set of $G$. It is clear that $X$ is not a restrained Steiner set of $G$ so that $s_r(G) \ge l-1$. It is easily observed that $X \cup \{v\}$, where $v \notin X$ is not a restrained Steiner set of $G$ so that $s_r(G) \ge l$. Let $y$ and $z$ be the two antipodal vertices of $x_i(1 \le i \le l-2)$. Then $W = X \cup \{y, z\}$ is a restrained Steiner set of $G$ and so $s_r(G) = l-2+2=l$.

**Case 2.** $r < d$. Let $C_{2r}: v_1, v_2, \dots, v_{2r}, v_1$ be a cycle of order $2r$ and let $P_{d-r+1}: u_0, u_1, u_2, \dots, u_{d-r}$ be a path of order $d-r+1$ and length $d-r$. Let $H$ be the graph obtained from $C_{2r}$ and $P_{d-r+1}$ by identifying $v_1$ in $C_{2r}$ and $u_0$ in $P_{d-r+1}$. Then add $l-2$ new vertices $w_1, w_2, \dots, w_{l-2}$ to $H$ and join each vertex $w_i$, ($1 \le i \le l-2$) to the vertex $u_{d-r-1}$ and obtain the graph $G$ of Figure 2.5.

<figure><img src="image_6.png" /><figcaption>Figure 2.5

$G$</figcaption></figure>

Then $\mathrm{rad}G = r$ and $\mathrm{diam}G = d$. Let $W = \{w_1, w_2, \dots, w_{l-2}, u_{d-r}\}$ be the set of all end vertices of $G$. By Theorem 2.4, $W$ is a subset of every restrained Steiner set of $G$. Since no vertex on the cycle $C_{2r}$ lies on the Steiner $W$-tree, we see that $W$ is not a restrained Steiner set of $G$. Let $W' = W \cup \{v_{r+1}\}$, where $v_{r+1}$ is the antipodal vertex of $u_{d-r}$ in $G$. Then it is clear that $W'$ is a restrained Steiner set of $G$. Hence $s_r(G) = l$. $\square$

In view of Theorem 2.6, we have the following realization result.

**Theorem 2.25.** Let $a, b$ and $p$ be integers such that $4 \le a \le b \le p$. Then there exists a connected graph $G$ of order $p$ with $s(G) = a$ and $s_r(G) = b$.
**Proof. Case 1.** $a=b$. Let $P_{p-a+1}: u_1, u_2, \dots, u_{p-a+1}$ be a path of order $p-a+1$. Let $G$ be the graph obtained from the path $P_{p-a+1}$ and the complete graph $K_{a-1}$ by joining each vertex of $K_{a-1}$ to the vertex $u_{p-a+1}$. The graph $G$ is shown in Figure 2.6 and its order is $p$. Now $W = V(K_{a-1}) \cup \{u_1\}$. By Theorem 1.1, $W$ is a subset of every Steiner set of $G$ and so $s(G) \ge a$. Since $S(W) = V$, $W$ is a Steiner set of $G$ and so $s(G) = a$. Since the subgraph $G[V-W]$ has no isolated vertices, $W$ is a restrained Steiner set of $G$. Thus $s_r(G) = a$.

<figure><img src="image_7.png" /><figcaption>Figure 2.6</figcaption></figure>

**Case 2.** $4 < a < b = p$. Let $G = K_{a,p-a}$ be the complete bipartite graph with partite sets $X = \{x_1, x_2, \dots, x_a\}$ and $Y = \{y_1, y_2, \dots, y_{p-a}\}$. By Theorems 1.2 and 2.14, we have $s(G) = a$ and $s_r(G) = b$.

**Case 3.** $4 < a < b < p$. Let $G_1 = K_{2,b-a}$ be the complete bipartite graph with partite sets $X = \{x_1, x_2\}$ and $Y = \{y_1, y_2, \dots, y_{b-a}\}$ and let $P: v_1, v_2, \dots, v_{p-b+1}$ be a path of order $p-b+1$. Let $H$ be the graph obtained from $G_1$ and $P$ by identifying the vertex $x_2$ in $G_1$ with the vertex $v_1$ in $P$ and subdividing the edge $x_1y_1$ of $G_1$ by the vertex $x$. Add $a-3$ new vertices $\{z_1, z_2, \dots, z_{a-3}\}$ to $H$ and join each vertex $z_i$ ($1 \le i \le a-3$) with the vertex $v_2$ and obtain the graph $G$ of order $p$ as shown in Figure 2.7.

<figure><img src="image_8.png" /><figcaption>Figure 2.7</figcaption></figure>
Let $Z = \{z_1, z_2, \dots, z_{a-3}, v_{p-b+1}\}$ be the set of all end vertices of $G$. First we show that $s_G(G) = a$. By Theorem 1.1, $Z$ is a subset of every Steiner set of $G$ and so $s(G) \ge a - 2$. Since $S(Z) \ne V$, $Z$ is not a Steiner set of $G$ and so $s(G) \ge a - 1$. It is easily verified that $Z \cup \{u\}$ where $u \notin Z$ is not a Steiner set of $G$ and so $s(G) \ge a$. However $W = Z \cup \{x_1, y_1\}$ is a Steiner set of $G$ so that $s(G) = a$. Next we show that $s_r(G) = b$. Since the subgraph $G[V - W]$ contains an isolated vertex, $W$ is not a restrained Steiner set of $G$. By Theorem 2.4, $Z$ is a subset of every restrained Steiner set of $G$. Let $W_1 = Z \cup Y$. It is easily seen that $W_1$ is not a restrained Steiner set of $G$ and so $s_r(G) \ge b - 1$. It is easily observed that $W_1 \cup \{v\}$ where $v \notin W_1$ is not a restrained Steiner set of $G$ and so $s_r(G) \ge b$. However $W_2 = W_1 \cup \{x, x_1\}$ is a restrained Steiner set of $G$ and so $s_r(G) = b$. $\square$

### 3 The restrained Steiner and the restrained geodetic numbers of a graph

**Example 3.1.** For the graph $G$ given in Figure 3.1, $W = \{v_1, v_4, v_6\}$ is a restrained Steiner set of $G$ so that $s_r(G) = 3$. Since the vertices $v_9$ and $v_{10}$ do not lie on a geodesic joining any pair of vertices of $W$, $W$ is not a restrained geodetic set of $G$ and so $g_r(G) \ge 4$. However $W = \{v_1, v_4, v_5, v_6\}$ is a restrained geodetic set of $G$ so that $g_r(G) = 4$.

<figure><img src="image_9.png" /><figcaption>Figure 3.1</figcaption></figure>
**Example 3.2.** For the graph $G$ given in Figure 3.2, $W = \{v_1, v_3, v_5\}$ is a restrained geodetic set of $G$ so that $g_r(G) = 3$. Since $v_4$ is a cut vertex of degree $4 = p-1$, by Theorem 2.20 we have $s_r(G) = 5$.

<figure><img src="image_10.png" /><figcaption>Figure 3.2</figcaption></figure>

From Examples 3.1 and 3.2, we see that there is no relation between $s_r(G)$ and $g_r(G)$. So we have the following realization result.

**Theorem 3.3.** For every pair of integers $a, b$ with $a \ge 3$ and $b \ge 3$, there exists a connected graph $G$ with $s_r(G) = a$ and $g_r(G) = b$.

*Proof.* For $a=b$, let $G$ be $K_{1,a-1}$. Then by Corollary 2.11 and Theorem 1.4, $s_r(G) = a$ and $g_r(G) = a$.

**Case 1.** $3 \le a < b$. Let $P: z_1, z_2, z_3, z_4, z_5, z_6, z_7$ be a path of order 7. Let $P_i: u_i, v_i, w_i$ ($1 \le i \le b-a$) be a copy of path of order 3. Let $H$ be the graph obtained from the paths $P$ and $P_i$ ($1 \le i \le b-a$) by joining the vertex $z_4$ with each $u_i$ ($1 \le i \le b-a$) and joining the vertices $z_1$ and $z_7$ with each $w_i$ ($1 \le i \le b-a$). Let $G$ be the graph obtained from $H$ by adding $a-2$ new vertices $x_1, x_2, \dots, x_{a-2}$ and joining $z_4$ with each $x_i$ ($1 \le i \le a-2$). The graph $G$ is shown in Figure 3.3.
<figure><img src="image_11.png" /><figcaption>Figure 3.3</figcaption></figure>

First we show that $s_r(G) = a$. Let $X = \{x_1, x_2, \dots, x_{a-2}\}$ be the set of all end vertices of $G$. By Theorem 2.4, $X$ is a subset of every restrained Steiner set of $G$. It is clear that $X$ is not a restrained Steiner set of $G$ so that $s_r(G) \ge a-1$. It is easily observed that $X \cup \{u\}$, where $u \notin X$ is not a restrained Steiner set of $G$ and so $s_r(G) \ge a$. However $W = X \cup \{z_1, z_7\}$ is a restrained Steiner set of $G$ so that $s_r(G) = a$. Next we show that $g_r(G) = b$. Since the vertices $u_i(1 \le i \le b-a)$ and $v_i(1 \le i \le b-a)$ do not lie on any geodesic joining a pair of vertices in $W$, $W$ is not a restrained geodetic set of $G$. Let $S$ be any restrained geodetic set of $G$. By Theorem 1.1, $X \subseteq S$. Since the vertices $u_i(1 \le i \le b-a)$ and $v_i(1 \le i \le b-a)$ lie on the $w_i - x_j(1 \le i \le b-a, 1 \le j \le a-2)$ geodesics, each $w_i(1 \le i \le b-a)$ belongs to $S$ and so $g_r(G) \ge a-2+b-a=b-2$. Since the vertices $z_2, z_3$ lie on $z_1 - x_i(1 \le i \le a-2)$ geodesic and, the vertices $z_5, z_6$ lie on $z_7 - x_i(1 \le
$i \le a - 2$) geodesic, $z_1$ and $z_7$ belong to $S$ and so $g_r(G) \ge b - 2 + 2 = b$. Let $S = W \cup \{w_1, w_2, \dots, w_{b-a}\}$. Then $S$ is a restrained geodetic set of $G$ so that $g_r(G) = a + b - a = b$.

**Case 2.** $b < a$ and $a \ne b + 1$. Let $P: x, y, z$ be a path of order 3. Add $b-2$ new vertices $y_1, y_2, \dots, y_{b-2}$ to the path $P$ and join each vertex $y_i$ ($1 \le i \le b-2$) with the vertex $y$ and obtain the graph $H$. Let $G$ be the graph obtained from $H$ by adding $a-b-1$ new vertices $h_1, h_2, \dots, h_{a-b-1}$ and joining each vertex $h_i$ ($1 \le i \le a-b-1$) with the vertices $x, y$ and $z$. The graph $G$ is shown in Figure 3.4.

<figure><img src="image_12.png" /><figcaption>Figure 3.4</figcaption></figure>

First we show that $g_r(G) = b$. Let $Y = \{y_1, y_2, \dots, y_{b-2}\}$ be the set of all end vertices of $G$. Since $Y$ is a subset of every restrained geodetic set, $g_r(G) \ge b-2$. It is easily seen that $Y$ is not a restrained geodetic set of $G$ and so $g_r(G) \ge b-1$. It is easily verified that $Y \cup \{v\}$, where $v \notin Y$ is not a restrained geodetic set of $G$ and so $g_r(G) \ge b$. However $W = Y \cup \{x, z\}$ is a restrained geodetic set of $G$ so that $g_r(G) = b$. Next we show that $s_r(G) = a$. Since the vertices $h_i$ ($1 \le i \le a-b-1$) do not lie on any Steiner W-tree, $W$ is not a restrained Steiner set of $G$. Since $y$ is a full degree cut vertex of $G$, it follows from Theorem 2.20 that $s_r(G) = a$.

**Case 3.** $a = b + 1$. Let $C: u_1, u_2, u_3, u_4, u_5, u_6$ be a cycle of order 6. Let $H$ be the graph obtained by joining the vertices $u_2$ and $u_6$ of the cycle $C$. Add $b-2$ new vertices $x_1, x_2, \dots, x_{b-2}$ to $H$ and join each vertex $x_i$ ($1 \le i \le b-2$ with the vertex $u_6$ and obtain the graph $G$ as shown in Figure 3.5.
<figure><img src="image_13.png" /><figcaption>Figure 3.5</figcaption></figure>

Let $X = \{x_1, x_2, \dots, x_{b-2}\}$ be the set of all end vertices of $G$. Since $X$ is a subset of every restrained geodetic set, $g_r(G) \ge b-2$. It is clear that $X$ is not a restrained geodetic set of $G$ and so $g_r(G) \ge b-1$. It is easily verified that $X \cup \{v\}$, where $v \notin X$ is not a restrained geodetic set of $G$ and so $g_r(G) \ge b$. However $S = X \cup \{u_1, u_4\}$ is a restrained geodetic set of $G$ so that $g_r(G) = b$. Next we show that $s_r(G) = b+1$. By Theorem 2.4, each $x_i(1 \le i \le b-2)$ belongs to every restrained Steiner set of $G$ and so $s_r(G) \ge b-2$. It is clear that $X$ is not a restrained Steiner set of $G$ and so $s_r(G) \ge b-1$. Also it is easily seen that neither $X \cup \{v\}$ nor $X \cup \{u, v\}$, where $u, v \notin X$ is a restrained Steiner set of $G$. However $W = X \cup \{u_1, u_3, u_4\}$ is a restrained Steiner set of $G$ so that $s_r(G) = b-2+3 = b+1$. Hence the proof. $\square$

## References

[1] H. Abdollahzadeh Ahangar, V. Samodivkin, S. M. Sheikholeslami and Abdollah Khodkar, The restrained geodetic number of a graph, *The Bulletin of the Malaysian Mathematical Society Series, 2* (2015), 1143–1155.

[2] F. Buckley and F. Harary, Distance in Graphs, *Addition-Wesley, Redwood City, CA*, 1990.
[3] M. Changat, A. K. Lakshmikuttyamma, J. Mathews, A note on 3 - Steiner intervals and betweenness, *Discrete Math.* **311** (22) (2011), 2601 – 2609.

[4] G. Chartrand, Oellermann, Ortred, Tian Song, Song Ling, Zou and Hung Kin, Steiner distance in graphs, *Caspopis pro Pestovani Matematiky* **114** (1989), 399 – 410.

[5] G. Chartrand, F. Harary and P. Zhang, On the geodetic number of a graph, *Networks* **39** (2002), 1 – 6.

[6] G. Chartrand, F. Harary and P. Zhang, The Steiner Number of a Graph, *Discrete Math.* **242** (2002), 41 – 54.

[7] D. P. Day, O. R. Oellermann, H. C. Swart, Steiner distance-hereditary graphs. *SIAMJ. Discrete Math.* **7** (1994), 437 – 442.

[8] R. Eballe, S. Canoy Jr., Steiner sets in the join and composition of graphs, *Congressus Numerantium*, **170** (2004), 65 – 73.

[9] F. Harary, Graph Theory, *Addition-Wesley*, 1969.

[10] F. Harary, E. Loukakis and C. Tsouros, The geodetic number of a graph, *Math. Comput. Modelling* **17** (1993), 89 – 95.

[11] C. Hernando, T. Jiang, M. Mora, I. M. Pelayo and C. Seara, On the Steiner, geodetic and hull number of graphs, *Discrete Math.* **293** (2005), 139 – 154.

[12] K. M. Kathiresan, S. Arockiaraj, R. Gurusamy and K. Amutha, On the Steiner radial number of graphs, *LNCS*, **7643** (2012), 65 – 72.

[13] Michael B. Frondoza and Sergio R. Canoy, Jr., The Edge Steiner Number of a Graph, *Bulletin of the Malays. Math. Sci. Soc.* (2) **35** (1) (2012), 53 – 59.

[14] O. R. Oellermann, Tian, Steiner centers in graphs, *Graph Theory* **14** (5), (1990), 585 – 597.

[15] P. A. Ostrand, Graphs with Specified radius and diameter, *Discrete Math.* **4** (1973), 71 – 75.

[16] I. M. Pelayo, Comment on "The Steiner number of a graph" by G. Chartrand and P. Zhang, *Discrete Math.* **242** (2002), 41 – 54.
[17] M. Raines, P. Zhang, The Steiner distance dimension of graphs, *Aus-tralasian J. Combin.* **20** (1999), 133 – 143.

[18] A. P. Santhakumaran and J. John, The Edge Steiner Number of a Graph, *Journal of Discrete Mathematical Science and Cryptography* **10** (2007), 677 – 696.

[19] A. P. Santhakumaran and J. John, The Upper Steiner Number of a Graph, *Graph Theory Notes of New York LIX*, (2010), 9 – 14.

[20] A. P. Santhakumaran and J. John, The forcing Steiner number of a graph, *Discussiones Mathematicae Graph Theory* **31** (2011), 171 – 181.

[21] A. P. Santhakumaran and J. John, The Forcing Geodetic and the Forcing Steiner Numbers of a Graph, *Discussiones Mathematicae Graph Theory* **31** (2011), 611 – 624.