On Roman balanced domination of graphs

1.   Introduction

Let $G = (V, E)$ be a graph. For a $v\in V$, we denote by $N(v)$ and $N[v]$ the neighbour set and closed neighbour set of $v$, i.e., $N(v) = \{u\in V|uv\in E\}$ and $N[v] = \{v\}\cup N(v)$. The size of $N(v)$ is denoted by $d(v)$ and refers to the degree of $v$ in $G$. The minimum and maximum degree of $G$ are denoted by $\delta(G)$ and $\Delta(G)$, respectively. For two subsets $A$ and $B$, we denote by $E(A, B)$ the set of the edges between $A$ and $B$ in $G$. In addition, we denote by $d_{G[A]}(v)$ and $E_{G[A]}$ the degree of $v$ and the set of edges in the induced graph $G[A]$, respectively. For $S\subset V$ and a function $f:V\rightarrow R$, we write $f(S) = \sum_{v\in S}f(v)$.

Graph domination is one of the fundamental concepts in graph theory and has wide applications. The notion of a dominating set can also be modeled as a function $f:V\rightarrow \{0, 1\}$ such that $f(N[v])\geq 1$ for each $v\in V$. Motivated by the problem of defending the Roman Empire ^[17], Cockayne et al.^[9] defined the notion of Roman dominating function (RDF) on a graph $G = (V, E)$ by $f:V\rightarrow \{0, 1, 2\}$ such that $f(N[v])\geq 1$ for each $v\in V$ and each vertex $u$ with $f(u) = 0$ has a neighbor $v$ with $f(v) = 2$. In recent years, this concept received further development, like total Roman dominating function ^[3], perfect and weak Roman dominating function ^[5,10,11,15], global Roman dominating function ^[6,7,13,14] and so on. For more related results, see ^{[1,2,4,8,12,16]}.

The notion of a balanced dominating function (BDF) is defined by a function $f:V\rightarrow \{-1, 0, 1\}$ that satisfies $f(N[u]) = 0$ for each $u\in V$, which was first introduced by Xu et al.^[19] in 2021. The balanced domination number of $G$ is therefore defined as the maximum weight of all BDF's in $G$ and is denoted by $\gamma_{\rm b}(G)$. Soon after, Xu and his collaborators proposed the notion of a balanced cycle dominating function; see ^[18].

Inspired by these aforementioned results, we define a new dominating function of a graph $G$, called the Roman balanced dominating function (RBDF), by $f:V\rightarrow \{-1, 0, 2\}$ which satisfies $f(N[v]) = 0$ for each $v\in V$. The maximum (resp. minimum) weight of all RBDF's on $G$ refers to the maximum (resp. minimum) Roman balanced domination number, denoted by $\gamma^{\rm M}_{\rm Rb}(G)$ (resp. $\gamma^{\rm m}_{\rm Rb}(G)$), that is,

By the definition of RBDF, the function $f = 0$ is trivially an RBDF for any $G$. Thus, for any $G$, we have $\gamma^{\rm M}_{\rm Rb}(G)\geq0$ and $\gamma^{\rm m}_{\rm Rb}(G)\leq0$. In particular, if $\gamma^{\rm M}_{\rm Rb}(G) = \gamma^{\rm m}_{\rm Rb}(G) = 0$ then we call $G$ Rd-balanced. Of course, there exists some graphs that are not Rd-balanced; see Figure 1, where the black vertices are presented as $2$ and the white vertices are presented as $-1$.

In this paper, we introduce the bounds on $\gamma^{\rm M}_{\rm Rb}(G)$ and $\gamma^{\rm m}_{\rm Rb}(G)$ with the maximal degree, the minimal degree, the order, and the size of edges of a graph $G$. Furthermore, we establish a relationship between the Roman balanced dominating function and the balanced dominating function, which is used for determining whether a graph is Rd-balanced or not. Finally, we give several classes of Rd-balanced graphs.

2.   Main results

In this section, we consider some bounds on $\gamma^{\rm M}_{\rm Rb}$ and $\gamma^{\rm m}_{\rm Rb}$. For an RBDF $f$ and $i\in \{-1, 0, 2\}$, let $A_i = \{v\in V: f(v) = i\}$, the size, of $A_0$, $A_2$, and $A_{-1}$ are denoted by $r$, $s$, and $t$, respectively. First, we provide the range of $s$ and $t$, which is useful in the following proof.

Lemma 1. For any RBDF $f$,

Proof. Let $n' = s+t$. Then $f(V) = 2s-t = 3s-n'\geq 3s-n$ as $n' = s+t\leq n$.

For any $u\in A_{-1}$, we have $|N[u]\cap A_2|\geq1$. Hence $|E(A_2, A_{-1})|\geq t$. That implies for $v\in A_2$, $|N[v]\cap A_{-1}|\geq \left\lceil \frac{t}{s}\right\rceil$. Note that $f(N[v]) = 0$ and $f(N[v]) = 2|N[v]\cap A_2|-|N[v]\cap A_{-1}|$. Therefore, $|N[v]\cap A_2|\geq \left\lceil \frac{t}{2s}\right\rceil$. Hence,

Since $n\geq n'\geq t$, we have $t\leq \frac{4n'-\sqrt{8n'+1}+1}{4}\leq \frac{4n-\sqrt{8n+1}+1}{4}$.

Similarly, we have $f(N[v]) = 0$ for any $v\in A_2$. Thus, $v$ has at least two neighbors belonging to $A_{-1}$, and $|E(A_{-1}, A_2)|\geq2s$. Therefore, we can find a vertex $u\in A_{-1}$, and we have $|N[u]\cap A_2|\geq\left\lceil \frac{2s}{t}\right\rceil$. Since $f(N[u]) = 0$ and $f(N[u]) = 2|N[u]\cap A_2|-|N[u]\cap A_{-1}|$, then we have

which implies that $(n'-s)^2 = t^2\geq4s$. Therefore, $s\leq n'+2-2\sqrt{n'+1}\leq n+2-2\sqrt{n+1}$ as $s\leq n$. □

Theorem 1. If $G$ has $n$ vertices, then we have

where the first (or the last) equality holds if and only if $G$ is $\Delta$-regular.

Proof. Let $f$ be a maximum RBDF of $G$ with the weight $\gamma^{M}_{Rb}(G)$. We find $s+t\leq n$ and $\gamma^{M}_{Rb}(G) = 2s-t$. By the definition of RBDF, $f(N[v]) = 0$ for any $v\in A_{2}$. Furthermore,

Thus, $2s = |E(A_{-1}, A_{2})|-4|E_{G[A_{2}]}|$. It is easy to get that $t = 2|E(A_{-1}, A_2)|-2|E_{G[A_{-1}]}|$ by the similar discussion. Thus,

Furthermore,

Combining with Eq (1), we have

where the last equality holds because $0 = \sum_{v\in A_0} f(N[v]) = |E(A_0, A_{-1})|-2|E(A_0, A_2)|$ for any $v\in A_0$.

Note that $\gamma^M_{Rb}(G) = 2s-t$. We have $2s-t\leq \Delta t- 2\delta s$, which means $s\leq \frac{\Delta+1}{2\delta +2} \cdot t$. Then

Since $\gamma^{M}_{Rb}(G) \geq 0$, we have $2s\geq t$, i.e. $t\leq \frac{2}{3}n$. Hence, $\gamma^{M}_{Rb}(G) \leq \frac{2(\Delta-\delta)n}{3(\delta+1)}$, as desired.

By a similar argument, we denote by $g$ a minimum RBDF of $G$ and $\gamma^{m}_{Rb}(G)$ the weight. Thus

Combining with (1), we have

Note that $\gamma^m_{Rb}(G) = 2s-t$. We have $2s-t\geq \delta t- 2\Delta s$, which means $s\geq \frac{\delta+1}{2\Delta +2} \cdot t$. Then

Since $\frac{\delta-\Delta}{\Delta+1} \leq 0$, then by Lemma 1, we have $\gamma^{m}_{Rb}(G) \geq \frac{(\delta-\Delta)(4n-\sqrt{8n+1}+1)}{4(\Delta+1)}$, as desired.

Finally, we consider the condition that makes the equality hold.

The sufficiency is obviously true. Now we prove the necessity. We only consider a graph $G$ satisfying $\gamma^{M}_{Rb}(G) = \frac{2(\Delta -\delta)n}{3(\delta+1)}$. For the case $\gamma^{m}_{Rb}(G) = \frac{(\delta-\Delta)(4n-\sqrt{8n+1}+1)}{4(\Delta+1)}$, the argument is similar. Above all, we may derive that $\gamma^{M}_{Rb}(G) = \frac{2(\Delta -\delta)n}{3(\delta+1)}$ with the following conditions holding:

(i) Each vertex in $A_{-1}$ (resp. $A_2$) has degree $\Delta$ (resp. $\delta$);

(ii) $s = \frac{1}{3}n$ and $t = \frac{2}{3}n$.

Let $v\in A_2$. The degree of every vertex in $A_2$ is $\delta$; that means $\delta = |E(\{v\}, A_2)|+|E(\{v\}, A_{-1})|$. Also, we know that $f(N[v]) = 2|E(\{v\}, A_2)|+2-|E(\{v\}, A_{-1})| = 0$. Thus $|E(\{v\}, A_{-1})| = \frac{2\delta+2}{3}$ and $|E(\{u\}, A_2)| = \frac{\Delta+1}{3}$ for every $u\in A_{-1}$ by the similar discussion. Thus for $|E(A_{-1}, A_2)|$, it is equal to

Note that $2s = t$. Then $\Delta = \delta$, which means $G$ is $\Delta$-regular. □

By the above theorem, we infer that the regular graph is $Rd$-balanced.

Theorem 2. If $G$ has $n\geq 3$ vertices, then $\gamma^{M}_{Rb}(G)\leq 2n+6-6\sqrt{n+1}$. The equality holds if and only if $G$ is obtained by adding edges between $K_{t}$ and $\frac{t^2}{4}K_{1}$ such that the degree of the vertex in $\frac{t^2}{4}K_{1}$ is $2$ and in $K_t$ is $\frac{t}{2}$, where $t = 2\sqrt{n+1}-2$.

Proof. Let $f$ be a maximum RBDF of $G$ with the weight $\gamma^{M}_{Rb}(G)$. By Lemma 1, we have $\gamma^{M}_{Rb}(G) = 2s-t = 3s-n'\leq 2n'+6-6\sqrt{n'+1}\leq 2n+6-6\sqrt{n+1}$.

The discussion of the equality can be divided into two parts as follows:

First, we demonstrate the necessity. Let $G$ satisfy $\gamma^{M}_{Rb}(G) = 2n+6-6\sqrt{n+1}$. By the proof of Lemma 1, the upper bound is tight if and only if $n = n'$, $s = \frac{t^2}{4}$. That means that $A_0 = \emptyset$ and $t = 2\sqrt{n+1}-2$. For any $u\in A_{-1}$, we observe that $2|N[u]\cap A_2| = |N[u]\cap A_{-1}|\leq |A_{-1}| = t$. Thus,

Since $|E(A_2, A_{-1})|\geq2s = \frac{t^2}{2}$, we obtain

Therefore, any vertex in $A_{-1}$ has just $\frac{t}{2}$ neighbours in $A_{2}$. Furthermore, since $|N[u]\cap A_{-1}| = t$, we have $G[A_{-1}] = K_{t}$. Similarly, $2|N[v]\cap A_2| = |N[v]\cap A_{-1}| = 2$, where $v$ is an arbitrary vertex in $A_2$, which means each vertex in $A_2$ has exactly $2$ neighbours in $A_{-1}$ and $G[A_2] = sK_1 = \frac{t^2}{4}K_1$, as desired.

Next, we demonstrate the sufficiency. Let $G$ be generated by adding edges between $K_{t}$ and $\frac{t^2}{4}K_{1}$, such that the degree of the vertex in $\frac{t^2}{4}K_{1}$ is $2$ and the degree of the vertex in $K_t$ is $\frac{t}{2}$. We know that $n = t+\frac{t^2}{4}$. Then we define $f'$:

Obviously, $f'$ is an RBDF of $G$. Then we have $\gamma^{M}_{Rb}(G)\geq f'(V) = \frac{t^2}{2}-t = 2n+6-6\sqrt{n+1}$. Above all, we have $\gamma^{M}_{Rb}(G) = 2n+6-6\sqrt{n+1}$. □

Theorem 3. If $G$ has $n\geq 3$ vertices, then $\gamma^{m}_{Rb}(G)\geq 3\lceil\frac{\sqrt{1+8n}-1}{4}\rceil-n$. Figure 1 ($d$) is an example that makes this bound tight.

Proof. Let $f$ be a minimum RBDF of $G$; the weight is $\gamma^{m}_{Rb}(G)$. The notation is like Lemma 1, $n': = s+t\leq n$ and $\gamma^{m}_{Rb}(G) = 3s-n'\geq 3s-n$.

For all $u\in A_{-1}$, we know that $|A_2\cap N[u]|\geq1$, hence $|E(A_2, A_{-1})|\geq t$. If $v\in A_2$, then $|N[v]\cap A_{-1}|\geq \left\lceil\frac{t}{s}\right\rceil$. Note that $0 = f(N[v]) = 2|A_2\cap N[u]|-|N[v]\cap A_{-1}|$. Hence $|A_2\cap N[u]|\geq \left\lceil\frac{t}{2s}\right\rceil$, thus

By the above inequality, we deduce that

Since $s$ is a nonnegative integer and $\gamma^{m}_{Rb}(G) = 3s-n'\geq 3\ \frac{\sqrt{1+8n'}-1}{4}-n'$, then for $n\geq 3$, we have $\gamma^{m}_{Rb}(G)\geq 3\ \frac{\sqrt{1+8n'}-1}{4}-n'\geq 3\ \frac{\sqrt{1+8n}-1}{4}-n$, hence the conclusion is true. □

By Theorem 2 and 3, let $\omega(f)$ be the weight of all RBDF's; then we have $3\lceil\frac{\sqrt{1+8n}-1}{4}\rceil-n\leq \omega(f)\leq 2n+6-6\sqrt{n+1}$, which gives the range of $\omega(f)$ about the order of the graph.

Theorem 4. If $G$ has $n$ vertices and $m$ edges, and each component is none of $K_1$, $K_2$, and Star, then

Proof. Let $f = (A_{-1}, A_0, A_2)$ be a minimum RBDF of $G$. Assume that $G$ contains exactly $k$ pendent vertices. We will show that Ineq (2) holds for $k = 0$, that is, $G$ contains no pendent vertex. Suppose that we have finished the proof when $k = 0$. Now we use induction on $n$. For $k\geq 1$, let $G$ delete all pendent vertices, denoted by $G'$. Since each component of $G$ is none of $K_1$, $K_2$, and Star, so is $G'$. Note that for the pendent vertex $v$, we have $f(v) = 0$. Thus $\gamma^{m}_{Rb}(G) = \gamma^{m}_{Rb}(G') > \frac{4}{7}(2|V(G')|-3|E(G')|)$ by the induction. Since $|V(G')| = n-k$ and $|E(G')| = m-k$, we have

as desired.

Now we prove Ineq (2) holds when $k = 0$. Let $A_{02} = A_0\cup A_2$, then we have $|E(A_{-1}, A_{02})|\geq|E(A_{-1}, A_2)|\geq|A_{-1}| = t$. Further, for $v\in A_2$, there is $f(v)+2d_{G[A_2]}(v)-d_{G[A_{-1}]}(v) = f(N_G[v]) = 0$. Thus, $d_{G[A_{-1}]}(v) = 2d_{G[A_2]}(v)+f(v) = 2d_{G[A_2]}(v)+2$. Recall that $r = |A_0|$, $s = |A_2|$, and $t = |A_{-1}|$. Hence,

where the last equality holds because $|E_{G[A_{02}]}| = |E_{G[A_{0}]}|+|E_{G[A_{2}]}|+|E(A_0, A_2)|$. So

Hence,

where $n_{02} = |A_{02}| = s+r$. Equivalently,

Therefore,

Let

We only need to show $\phi(r)\geq0$, then we have $\gamma_{Rb}^m(G)\geq\frac{4}{7}(2n-3m)$. If $r = 0$, then $\phi(r) = 0$. Then let $r\geq1$. If $v\in A_0$ and $d_{G[A_{02}]}(v) = 0$, according to the assumption that $G$ contains no $K_1$, then we obtain $d(v)\geq1$, and all of the neighbors of $v$ are contained in $V_{-1}$. However, $f(N[v])\leq-1$ now, we obtain a contradiction. Hence, we have $v\in V_0$, and $d_{G[A_{02}]}(v)\geq1$. Thus,

Let $X = \{d_{G[A_{02}]}(v)\geq 2:v\in A_0\}$ and $Y = \{d_{G[A_{02}]}(v) = 1:v\in A_0\}$. Then $r = |X|+|Y|$. Combining with $|E(A_0, A_2)| = \sum_{v\in A_0}d_{G[A_2]}(v)$, we can consider Eq (3) in two parts as follows:

where the first inequality holds as $d_{G[A_{02}]}(v)\geq d_{G[A_{0}]}(v)$ and $d_{G[A_2]}(v)\geq 0$ for each $v\in A_0$. Now we focus on an arbitrary vertex $v$ in $Y$. Then either $d_{G[A_0]}(v) = 1$ or $d_{G[A_2]}(v) = 1$. If we suppose $d_{G[A_0]}(v) = 1$, then $v$ must be a pendent vertex, which contradicts $G$ having no pendent vertices. So $d_{G[A_0]}(v) = 0$ and $d_{G[A_{02}]}(v) = d_{G[A_2]}(v) = 1$ for each $v\in Y$. By Ineq (4), we have

and so $\gamma^{m}_{Rb}(G) > \frac{4}{7}(2n-3m)$, as desired. □

Theorem 5. If $f$ is an RBDF of $G$, then there is a BDF $g$ of $G'$ satisfying the weight of them is equal, where $G'$ is obtained by adding edges between $G$ and a copy $G^*$ of $G$; any $v\in V$ is adjacent to the copies of all vertices in $N[v]$. Further, $\gamma^{M}_{Rb}(G)\leq \gamma_{b}(G')$ and $\gamma^m_{Rb}(G)\geq -\gamma_{b}(G')$.

Proof. Denote $V(G') = \{v_1: v\in V(G)\}\cup \{v_2: v\in V(G^*)\}$. There are three situations. If $f(v) = 0$, we say $g(v_1) = g(v_2) = 0$. If $f(v) = -1$, then let $g(v_1) = -1$ and $g(v_2) = 0$. If $f(v) = 2$, then $g(v_1) = g(v_2) = 1$. Obviously, $g(v_1)+g(v_2) = f(v)$. Then we have $g(N[v_1]) = g(N[v_2]) = \sum_{u\in N[v]}\left (g(u_1)+g(u_2)\right) = f(N[v])$. Hence, $g$ is a BDF of $G'$ satisfying the weight of $f$ and $g$ are equal.

Now we choose $f$ a maximum RBDF of $G$,

Similarly, we have $\gamma^m_{Rb}(G)\geq -\gamma_{b}(G')$. □

Remark 1. By the above theorem, if $G'$ is $d$-balanced, that is $\gamma_{b}(G') = 0$, then we have $\gamma^M_{Rb}(G) = \gamma^m_{Rb}(G) = 0$. So $G$ is also $Rd$-balanced.

Remark 2. By Theorem 2.4 of ^[19] and Theorem 5, $\gamma^{M}_{Rb}(G)\leq\gamma_b(G')\leq 2n-2\gamma(G')$. Furthermore, there is $\gamma(G) = \gamma(G')$, thus $\gamma^M_{Rb}(G)\leq 2n-2\gamma(G)$. The equality holds when $G$ contains only isolated vertices.

Proposition 6. $f(V)$ is even.

Proof. For an RBDF, we have $\sum_{v\in A_{-1}} f(N[v]) = 0$, and

Note that $f(N_{G[A_0\cup A_2]}(v))$ and $\sum_{v\in A_{-1}}f(N_{G[A_{-1}]}(v)) = 2E_{G[A_{-1}]}$ are both even. Thus,

as desired. □

Proposition 7. A forest is $Rd$-balanced.

Proof. We only need to show each tree $G$ is $Rd$-balanced. Since $f$ is an RBDF of $G$, it is clear that for any $v\in V$, $f(N[v]) = 0$.

Note that for each $uv\in E$, $f(u)+f(v) = 0$ if and only if both items are zero. This means every leaf $v\in G$ satisfies $f(v) = 0$, then we delete all leaves, denoted by $G'$. $G'$ is still a tree, and all leaves of $G'$ are in $V_0$ by a similar argument. By deleting leaves from $G$ repeatedly, we find that every vertex in $G$ is in $V_0$. Hence, $G$ is $Rd$-balanced, as desired. □

In addition, the regular graph is $Rd$-balanced, as mentioned before.

Some $d$-balanced graphs are shown by Xu et al.^[19]. By the same argument, we can obtain that if the graph meets one of the following conditions, it is $Rd$-balanced.

(i) $\Delta(G) = n-1$;

(ii) $G$ is a generalized ladder graph of order 2$n$;

(iii) $G$ is a complete multipartite graph;

(iv) $G$ is a join graph of path and cycle, or path and path, or cycle and cycle.

Remark 3. We can also give a join graph $G$ that is not $Rd$-balanced, for example; see Figure 2. We find that $G\vee G$ with the given labelling in $G$ satisfies $\gamma_{Rb}^m(G\vee G) = -2$.

3.   Conclusions

In this paper, firstly, we provide the notion of Roman balanced dominating function, which generates two concepts in graph theory: Roman domination function and balance domination function. Then we give some upper and lower bounds on the maximum and minimum Roman balanced domination number of the graph, in terms of the minimum degree, the maximum degree, the order, and the size of the edges of the graph. Finally, we determine some graphs that are Rd-balanced.

Author contributions

M. Y. Zhang: Conceptualization, Investigation, Methodology, Writing-original draft, Writing-review, editing. J. X. Zhang: Conceptualization, Methodology, Supervision, Writing-review, editing.

Conflict of interest

The authors declare that they have no conflicts of interest.

Use of Generative-AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.