Characterization of trees with Roman bondage number 1

1.   Introduction

For terminology and notation on graph theory not given here, the reader is referred to Xu ^[14]. Let $G = (V, E)$ be a finite, undirected and simple graph, where $V = V(G)$ is the vertex set and $E = E(G)$ is the edge set of $G$. For a vertex $x\in V(G)$, let $N_G(x) = \{y\in V(G): xy\in E(G)\}$ be the open set of neighbors of $x$ and $N_G[x] = N_G(x)\cup \{x\}$ be the closed set of neighbors of $x$, $E_G(x) = \{xy\in E(G):\, y\in N_G(x)\}$ and $d_G(x) = |E_G(x)|$ be the vertex degree of $x$.

A subset $D\subseteq V$ is a dominating set of $G$ if every vertex in $V-D$ has at least one neighbor in $D$. The domination number of $G$, denoted by $\gamma(G)$, is the minimum cardinality among all dominating sets of $G$. The domination is an important and classic notion that has become one of the most widely researched topics in graph theory. A thorough study of domination appears in the books ^[7,8] by Haynes, Hedetniemi, and Slater. Among various problems related to the domination number, some focus on graph alterations and their effects on the domination number. Here, we are concerned with the removal of edges from a graph. The bondage number of $G$, denoted by $b(G)$, is the minimum number of edges whose removal from $G$ results in a graph with domination number larger than that of $G$. The bondage number was introduced by Fink et at. ^[5] in 1990. The bondage number are an important parameters for measuring the vulnerability and stability of the network domination under link failure. Xu ^[15] gave a review article on bondage numbers in 2013.

The Roman dominating function (RDF) on $G$, proposed by Stewart ^[13], is a function $f: V\rightarrow\{0, 1, 2\}$ such that each vertex $x$ with $f(x) = 0$ is adjacent to at least one vertex $y$ with $f(y) = 2$. For $S\subseteq V$ let $f(S) = \sum\limits_{u\in S} f(u)$. The value $f(V(G))$ is called the weight of $f$, denoted by $f(G)$. The Roman domination number, denoted by $\gamma_{\rm R}(G)$, is defined as the minimum weight of all Roman dominating functions, that is,

A Roman dominating function $f$ is called to be a minimum Roman dominating function (MRDF) if $f(G) = \gamma_{\rm R}(G)$.

The Roman bondage number, denoted by $b_{\rm R}(G)$, proposed by Rad and Volkmann ^[9], of a nonempty graph $G$ is the minimum number of edges whose removal from $G$ results in a graph with larger Roman domination number. Precisely speaking, the Roman bondage number

Roman domination number has been well studied ^[3,4].

An edge set $B\subseteq E(G)$ that $\gamma_{\rm R}(G-B) > \gamma_{\rm R}(G)$ is called the Roman bondage set and the minimum one is called the minimum Roman bondage set. In ^[2], the authors showed that the decision problem for $b_{\rm R}(G)$ is NP-hard even for bipartite graphs. The Roman bondage number has been further studied for example in ^{[1,6,11,10,12]}.

In 2001, Rad and Volkmann ^[9] proved that the Roman bondage number for trees is no more than 3. They proposed a problem that is to determine the trees with Roman bondage number 1. In this paper, we characterize trees with Roman bondage number $1$.

2.   Preliminary results

Let $f = (V_0, V_1, V_2)$ be a Roman dominating function of $G$ where $V_i = \{v\in V(G):\, f(v) = i\}$ for $i = 0, 1, 2$. Let $u\in V(G)$ and $f(u) = 2$, the private neighborhood of $u$ with respect to $f$ is defined as the set

Clearly $PN(u, f, G)\ne \emptyset$ when $f$ is a MRDF of $G$. A vertex $u$ is called universal iff $f(u) = 2$ for each MRDF $f$ of $G$. A vertex $u$ is called idle iff $f(u) = 0$ for each MRDF $f$ of $G$.

Proposition 2.1.[Rad et al. ^[6,11]] If $u$ is universal or idle in graph $G$, then $b_R(G)\le d_G(u)$. Moreover, $\gamma_R(G) = \gamma_R(G-u)$ if $u$ is idle.

Proposition 2.2. If $u$ is idle in graph $G$, then $b_R(G)\le b_R(G-u)$.

Proof. Let $u$ be an idle vertex of graph $G$. Let $B\subseteq E(G-u)$ be a minimum Roman bondage set of $G-u$. Then $\gamma_R(G-u-B) > \gamma_R(G-u)$. We claim that $B$ is also a Roman bondage set of $G$. Suppose to the contrary that $\gamma_R(G-B) = \gamma_R(G)$. Then $u$ is idle of $G-B$. By Proposition 2, we have $\gamma_R(G-B) = \gamma_R(G-B-u)$. Hence $\gamma_R(G-u-B) = \gamma_R(G) = \gamma_R(G-u)$, a contradiction with $\gamma_R(G-u-B) > \gamma_R(G-u)$. Therefore $b_R(G)\le b_R(G-u)$.

Proposition 2.3. Let $T$ be a tree, $N(u) = N_T(u) = \{u_1, u_2, \ldots, u_s\}$ be the open neighborhood of $u$ in $T$ and $T_i$ be the connected component of $T-u$ that contains $u_i$ for each $i = 1, 2, \ldots, s$. If $u$ is idle in $T$ and there exists a MRDF $f$ of $T$ such that at least $\min\{s, 3\}$ vertices in $N(u)$ can be assigned 2, then $b_R(T) = \min\{s, b_R(T_i):\, i = 1, 2, \ldots, s\}$.

Proof. Since $u$ is idle in $T$, $s\ge 1$. By Proposition 2, $\gamma_R(T) = \gamma_R(T-u) = \sum_{i = 1}^s \gamma_R(T_i)$ and $b_R(T)\le \min\{d_T(u), b_R(T-u)\} = \min\{s, b_R(T_i):\, i = 1, 2, \ldots, s\}$. If $\min\{s, b_R(T_i):\, i = 1, 2, \ldots, s\} = 1$, then $b_R(T) = 1$.

Next assume $s\ge 2$ and $b_R(T_i)\ge 2$ for each $i = 1, 2, \ldots, s$. Since there exists a MRDF $f$ of $T$ such that at least $\min\{s, 3\}\ge 2$ vertices in $N(u)$ can be assigned 2, $\gamma_R(T-uu_j) = \gamma_R(T)$ for each positive integer $j$ with $1\le j\le s$. Let $e\in E(T_j)$ for some $1\le j\le s$, we have $\gamma_R(T_j-e) = \gamma_R(T_j)$ since $b_R(T_j)\ge 2$. Because there exists a MRDF $f$ of $T$ such that at least $\min\{s, 3\}\ge 2$ vertices in $N(u)$ can be assigned 2, there exists some $1\le k\ne j\le s$ and a MRDF $f$ of $T$ such that $f(u_k) = 2$. Then $f|_{T_i}$ is a MRDF of $T_i$ for $i\ne j$. Therefore $\gamma_R(T-e)\le \gamma_R(T_j-e)+\sum_{i = 1, i\ne j}^s\gamma_R(T_i) = \sum_{i = 1}^s \gamma_R(T_i) = \gamma_R(T)$. Hence $b_R(T) > 1$. If $\min\{s, b_R(T_i):\, i = 1, 2, \ldots, s\} = 2$, then $b_R(T) = 2$.

At last assume $s\ge 3$ and $b_R(T_i) = 3$ for each $i = 1, 2, \ldots, s$. For any two different edges $e_1, e_2\in E(T)$ and without loss of generality assume $e_j = uu_{i_j}$ or $e_j\in E(T_{i_j})$ for $j = 1, 2$ and $1\le i_j\le s$ (admits $i_1 = i_2$), we have $\gamma_R(T_{i_j}-e_1-e_2) = \gamma_R(T_{i_j})$ since $b_R(T_{i_j}) = 3$. Because there exists a MRDF $f$ of $T$ such that at least $\min\{s, 3\} = 3$ vertices in $N(u)$ can be assigned 2, there exists some $1\le k\ne i_1, i_2\le s$ and a MRDF $f$ of $T$ such that $f(u_k) = 2$. Then $f|_{T_i}$ is a MRDF of $T_i$ for $i\ne i_1, i_2$. Therefore $\gamma_R(T-e_1-e_2)\le \gamma_R(T_{i_1}-e_1)+\gamma_R(T_{i_2}-e_2)+\sum_{i = 1, i\ne i_1, i_2}^s\gamma_R(T_i) = \sum_{i = 1}^s \gamma_R(T_i) = \gamma_R(T)$. Hence $b_R(T)\ge 2$. Thus $b_R(T) = 3$.

We show a useful result in the following.

Theorem 3.1.[Rad et al. ^[6,11]] Let $G$ be a graph and $e = uv\in E(G)$. Then $\gamma_R(G-e) > \gamma_R(G)$ iff $f(u) = 2$ and $v\in PN(u, f, G)$ or $f(v) = 2$ and $u\in PN(v, f, G)$ for each MRDF $f$ of $G$.

3.   Trees with Roman bondage number 1

Lemma 3.1. Let $T$ be any tree. If there exists an universal vertex $u\in V(G)$, then there exists $v\in N_T(u)$ such that $\gamma_R(T-uv) > \gamma_R(T)$.

Proof. Let $N_T(u) = \{u_1, u_2, \ldots, u_k\}$. Suppose to the contrary that $\gamma_R(T-uu_i) = \gamma_R(T)$ for each $i = 1, 2, \ldots, k$. For each $i = 1, 2, \ldots, k$, let $T_i$ be the connected component of $T-uu_i$ which contains $u_i$ and $f_i$ be a MRDF of $T-uu_i$. By definition, $f_i(V(T_i)) = \gamma_R(T_i)$ for each $i$.

Let $f$ be any MRDF of $T$. Then $f(u) = 2$ since $u$ is universal. If for all $i\in \{1, 2, \ldots, k\}$, $f_i(V(T_i))\le f(V(T_i))$, then let

Then $f'$ is a RDF of $T$ with $f'(V(T)) = \sum_i^k f_i(V(T_i))+1 < \sum_i^k f(V(T_i))+2 = f(V(T))$, a contradiction. Thus there exists some positive integer $j$ with $1\le j\le k$ such that $f_j(V(T_j)) > f(V(T_j))$.

Let

Since $f_j$ is a MRDF of $T$ and $u$ is universal, $f_j(u) = 2$ and hence $f''$ is also a RDF of $T$. However $f''(V(T)) = f(V(T_j))+f_j(V-V(T_j)) < f_j(V(T_j))+f_j(V-V(T_j)) = f_j(V(T)) = \gamma_R(T)$, a contradiction. Therefore there exists $v\in N_T(u)$ such that $\gamma_R(T-uv) > \gamma_R(T)$.

A vertex $u$ is called free in $G$ if any MRDF $f$ have $f(u)\ne 1$ and there exist MRDFs $f_1$ and $f_2$ such that $f_1(u) = 0$ and $f_2(u) = 2$.

Proposition 2.2. Let $e = uv$ be an edge in tree $T$. If both $u$ and $v$ are free vertices, and $f(N_T(u)\cup N_T(v)-\{u, v\})\le 1$ for any MRDF $f$. Then $\gamma_R(T-uv) > \gamma_R(T)$.

Proof. Let $f$ be any MRDF of $T$. Since both $u$ and $v$ are free vertices and $f(N_T(u)\cup N_T(v)-\{u, v\})\le 1$, $\{f(u), f(v)\} = \{0, 2\}$ or $f(u) = f(v) = 2$. We claim that $\{f(u), f(v)\} = \{0, 2\}$. Suppose to the contrary that there exists a MRDF $f_1$ of $T$ such that $f_1(u) = f_1(v) = 2$. Then $|PN(u, f_1, T)|\ge 2$ and $|PN(v, f_1, T)|\ge 2$. Let $N_T(u) = \{v, u_1, u_2, \ldots, u_k\}$, $k\ge 2$ since $|PN(u, f_1, T)|\ge 2$. There exists a MRDF $f_1'$ of $T$ such that $f_1'(u) = 0$ and $f_1'(v) = 2$ because $u$ is a free vertex and $f_1'(N(u)\cup N(v)-\{u, v\})\le 1$. Let $T_u$ and $T_v$ be the two connected components of $T-uv$ that contain $u$ and $v$, respectively. Note that $f_1(T_v) = f_1'(T_v)$ and $f_1(T_u) = f_1'(T_u)$. Let $T_{u_i}$ be the connected component of $T-uu_i$ that contains $u_i$ for each $i = 1, 2, \ldots, k$. Since $T$ is a tree, $f_1'(T_{u_i}) = \gamma_R(T_{u_i})\ge f_1(T(u_i))$ for each $i$ with $1\le i\le k$.

Since $f_1(T_u) = f_1'(T_u)$, $f_1(u) = 2$ and $f_1'(u) = 0$, there exists some positive integer $j$ with $1\le j\le k$ such that $f_1'(T(u_j)) = f_1(T(u_j)) +2$, or there exist two positive integers $p$ and $q$ with $1\le p, q\le k$ such that $f_1'(T(u_p)) = f_1(T(u_p)) +1$ and $f_1'(T(u_q)) = f_1(T(u_q)) +1$. If there exists some positive integer $j$ with $1\le j\le k$ such that $f_1'(T(u_j)) = f_1(T(u_j)) +2$, then denote

Note that $f_2$ is a Roman dominating function of $T$. Since $f_2(T) = f_1'(T-T_{u_j})+f_1(T_{u_j})+2 = f_1'(T-T_{u_j})+f_1'(T(u_j)) = f_1'(T)$, $f_2$ is a MRDF of $T$. However, $f_2(u_j) = 2$ is a contradiction with $f_2(N_T(u)\cup N_T(v)-\{u, v\})\le 1$. If there exist two positive integers $p$ and $q$ with $1\le p, q\le k$ such that $f_1'(T(u_p)) = f_1(T(u_p)) +1$ and $f_1'(T(u_q)) = f_1(T(u_q)) +1$, then denote

Note that $f_3$ is a Roman dominating function of $T$. Since $f_3(T) = f_1'(T-T_{u_p}-T_{u_q})+f_1(T_{u_p})+f_1(T_{u_q})+1+1 = f_1'(T-T_{u_p}-T_{u_q})+f_1'(T(u_p))+f_1'(T(u_q)) = f_1'(T)$, $f_3$ is a MRDF of $T$. However, $f_3(u_p) = f_3(u_q) = 1$ is a contradiction with $f_3(N_T(u)\cup N_T(v)-\{u, v\})\le 1$. Therefore $\{f(u), f(v)\} = \{0, 2\}$ for any MRDF $f$ of $T$.

Let $f$ be any MRDF of $T$. Then $\{f(u), f(v)\} = \{0, 2\}$. Since $f(N_T(u)\cup N_T(v)-\{u, v\})\le 1$, $v\in PN(u, f, T)$ if $f(u) = 2$ or $u\in PN(v, f, T)$ if $f(v) = 2$. By Theorem 2, $\gamma_R(T-uv) > \gamma_R(T)$.

Theorem 3.1. Let $T$ be a tree. $b_R(T) = 1$ iff $T$ has a universal vertex $w$, or

there exists an edge $e = uv$ such that both $u$ and $v$ are free vertices, and $f(N_T(u)\cup N_T(v)-\{u, v\})\le 1$ for any MRDF $f$ of $T$.

Proof. The sufficiency comes from Lemmas 3 and 3. Next we show the necessity. Assume there are no universal vertices in $T$. Since $b_R(T) = 1$, there exists an edge $e = uv$ such that $\gamma_R(T-uv) > \gamma_R(T)$. Let $f$ be any MRDF of $T$. By Theorem 2, $f(u) = 2$ and $v\in PN(u, f, T)$ or $f(v) = 2$ and $u\in PN(v, f, T)$. We have both $u$ and $v$ are free vertices since both of them are not universal vertices.

We only need to show $f(N_T(u)\cup N_T(v)-\{u, v\})\le 1$. Suppose to the contrary that $f(N_T(u)\cup N_T(v)-\{u, v\})\ge 2$. Without loss of generality assume $f(u) = 2$ and $v\in PN(u, f, T)$. Since $u$ and $v$ are free vertices, there exists a MRDF $f'$ of $T$ such that $f'(v) = 2$ and $u\in PN(v, f', T)$. We claim that $f(N_T(u)) = 0$. Otherwise there exists a vertex $w\in N(u)$ such that $f(w) = 2$ since $f(u) = 2$. Let $T_w$ be the connected component of $T-uw$ which contains $w$. Then $f|_{T_w}$ is a MRDF of $T_w$. Also $f'|_{T_w}$ is a MRDF of $T_w$. Denote

Clearly $f''$ is a MRDF of $T$. However, $f''(u) = 0$ and $f''(v) = f''(w) = 2$ is a contradiction with $u\in PN(v, f'', T)$ by Theorem 2. Thus $f(N_T(u)) = 0$ and $f(N_T(v)-u)\ge 2$. Since $v\in PN(u, f, T)$, there exists at least two vertices $s$ and $t$ in $N_T(v)-u$ such that $f(s) = f(t) = 1$. Denote

Clearly $f_1$ is a MRDF of $T$. However, $f_1(u) = f_1(v) = 2$, a contradiction with $v\in PN(u, f, T)$. Therefore $f(N_T(u)\cup N_T(v)-\{u, v\})\le 1$.

4.   Conclusions

We characterize trees with Roman bondage number 1 in the above paragraph. Since $b_R(T)\le 3$ for tree $T$, we have tried to obtain the similar results for $b_R(T)$ equals to $2$ or $3$. Unfortunately, it seems very difficult or we can not get similar results for $b_R(T)$ equals to $2$ or $3$. Indeed, it may be much easier to deal with $b_R(T) = 3$. But the similar method does not work. We will try to find other method to study the cases of $b_R(T)$ equals to $2$ or $3$.

Acknowledgments

The authors would like to express their gratitude to the anonymous referees for their critical commons and helpful suggestions on the original manuscript, which resulted in this version.

This research was supported by NNSF of China (No. 11401004) and Anhui Provincial Natural Science Foundation (No. 1708085MA01).

Conflict of interest

The authors declare no conflict of interest.