A destination-preserving model for simulating Wardrop equilibria in traffic flow on networks

1.   Introduction

In this paper, we shall only consider graphs without multiple edges or loops. Let $ G = (V(G), E(G)) $ be a graph, $ v \in V(G) $, the neighborhood of $ v $ in $ G $ is denoted by $ N(v) $. That is to say $ N(v) = \{u| uv \in E(G), u \in V(G)\} $. The degree of a vertex $ v $ is denoted by $ d(v) $, i.e. $ d(v) = |N(v)| $. A graph is trivial if it has a single vertex. The maximum degree and the minimum degree of a graph $ G $ are denoted by $ \Delta(G) $ and $ \delta(G) $, respectively. Denote by $ K_n $ the complete graph on $ n $ vertices.

A subset $ D $ of the vertex set of a graph $ G $ is a dominating set if every vertex not in $ D $ has at least one neighbor in $ D $. The domination number $ \gamma(G) $ is the minimum cardinality of a dominating set of $ G $. A dominating set $ D $ of $ G $ with $ |D| = \gamma(G) $ is called a $ \gamma $-set of $ G $.

Roman domination of graphs is an interesting variety of domination, which was proposed by Cockayne et al. ^[6]. A Roman dominating function (RDF) of a graph $ G $ is a function $ f: V(G) \rightarrow \{0, 1, 2\} $ such that every vertex $ u $ for which $ f(u) = 0 $ is adjacent to at least one vertex $ v $ for which $ f(v) = 2 $. The weight $ w(f) $ of a Roman dominating function $ f $ is the value $ w(f) = \sum_{u \in V(G)}f(u) $. The minimum weight of an RDF on a graph $ G $ is called the Roman domination number $ \gamma_R(G) $ of $ G $. An RDF $ f $ of $ G $ with $ w(f) = \gamma_{R}(G) $ is called a $ \gamma_{R} $-function of $ G $. The problems on domination and Roman domination of graphs have been investigated widely, for example, see list of references ^[8,9,10,13] and ^[3,7,12], respectively.

In 2016, Chellali et al. ^[5] introduced a variant of Roman dominating functions, called Roman {2}-dominating functions. A Roman $\{ 2 \}$-dominating function (R$\{ 2 \}$DF) of $ G $ is a function $ f: V\rightarrow \{0, 1, 2\} $ such that $ \sum_{u\in N(v)}f(u)\geq 2 $ for every vertex $ v\in V $ with $ f(v) = 0 $. The weight of a Roman {2}-dominating function $ f $ is the sum $ \sum_{v\in V}f(v) $. The Roman {2}-domination number $ \gamma_{\{R2\}}(G) $ is the minimum weight of an R{2}DF of $ G $. Note that if $ f $ is an R{2}DF of $ G $ and $ v $ is a vertex with $ f(v) = 0 $, then either there is a vertex $ u\in N(v) $ with $ f(u) = 2 $, or at least two vertices $ x, y \in N(v) $ with $ f(x) = f(y) = 1 $. Hence, an R{2}DF of $ G $ is also an RDF of $ G $, which is also mentioned by Chellali et al ^[5]. Moreover, they showed that the decision problem for Roman {2}-domination is NP-complete, even for bipartite graphs.

In fact, a Roman {2}-dominating function is essentially the same as a weak $ \{2\} $-dominating function, which was introduced by Brešar et al. ^[1] and studied in literatures ^[2,11,14,15].

For a mapping $ f:V(G)\rightarrow \{0, 1, 2\} $, let $ (V_0, V_1, V_2) $ be the ordered partition of $ V(G) $ induced by $ f $ such that $ V_i = \{x: f(x) = i\} $ for $ i = 0, 1, 2 $. Note that there exists a 1-1 correspondence between the function $ f $ and the partition $ (V_0, V_1, V_2) $ of $ V(G) $, so we will write $ f = (V_0, V_1, V_2) $.

Chellali et al. ^[4] obtained the following lower bound of Roman domination number.

Lemma 1. (Chellali et al. ^[4]) Let $ G $ be a nontrivial connected graph with maximum degree $ \Delta $. Then $ \gamma_{R}(G)\geq\frac{\Delta+1}{\Delta}\gamma(G) $.

In this paper, we generalize this result on nontrivial connected graph $ G $ with maximum degree $ \Delta $ and minimum degree $ \delta $. We prove that $ \gamma_{R}(G)\geq\frac{\Delta+2\delta}{\Delta+\delta}\gamma(G) $. As a corollary, we obtain that $ \frac{3}{2}\gamma(G)\leq\gamma_{R}(G)\leq 2\gamma(G) $ for any nontrivial regular graph $ G $. Moreover, we prove that $ \gamma_{R}(G)\leq2\gamma_{\{R2\}}(G)-1 $ for every graph $ G $ and there exists a graph $ I_k $ such that $ \gamma_{\{R2\}}(I_k) = k $ and $ \gamma_{R}(I_k) = 2k-1 $ for any integer $ k\geq2 $.

2.   A lower bound of Roman domination number

Lemma 2. (Cockayne et al. ^[6]) Let $ f = (V_0, V_1, V_2) $ be a $ \gamma_{R} $-function of an isolate-free graph $ G $ with $ |V_1| $ as small as possible. Then

(i) No edge of $ G $ joins $ V_1 $ and $ V_2 $;

(ii) $ V_1 $ is independent, namely no edge of $ G $ joins two vertices in $ V_1 $;

(iii) Each vertex of $ V_0 $ is adjacent to at most one vertex of $ V_1 $.

Theorem 3. Let $ G $ be a nontrivial connected graph with maximum degree $ \Delta(G) = \Delta $ and minimum degree $ \delta(G) = \delta $. Then

Moreover, if the equality holds, then

Proof. Let $ f = (V_0, V_1, V_2) $ be a $ \gamma_{R} $-function of $ G $ with $ V_1 $ as small as possible. By Lemma 2, we know that $ N(v)\subseteq V_0 $ for any $ v\in V_1 $ and $ N(v_1)\cap N(v_2) = \emptyset $ for any $ v_1, v_2\in V_1 $. So we have

Since $ G $ is nontrivial, it follows that $ V_2\neq \emptyset $. Note that every vertex in $ V_2 $ is adjacent to at most $ \Delta $ vertices in $ V_0 $; we have

By Formulae (2.2) and (2.3), we have

By the definition of an RDF, every vertex in $ V_0 $ has at least one neighbor in $ V_2 $. So $ V_1\cup V_2 $ is a dominating set of $ G $. Together with Formula (2.4), we can obtain that

Note that $ f $ is a $ \gamma_{R} $-function of $ G $; we have

Moreover, if the equality in Formula (2.1) holds, then by previous argument we obtain that $ |V_1| = \frac{|V_0|}{\delta} $, $ |V_0| = \Delta|V_2| $, and $ V_1\cup V_2 $ is a $ \gamma $-set of $ G $. Then we have

Hence, we have

So

since $ V_1\cup V_2 $ is a $ \gamma $-set of $ G $. This completes the proof.

Now we show that the lower bound in Theorem 3 can be attained by constructing an infinite family of graphs. For any integers $ k\geq 2 $, $ \delta\geq 2 $ and $ \Delta = k\delta $, we construct a graph $ H_k $ from $ K_{1, \Delta} $ by adding $ k $ news vertices such that each new vertex is adjacent to $ \delta $ vertices of $ K_{1, \Delta} $ with degree 1 and no two new vertices has common neighbors. Then add some edges between the neighbors of each new vertex $ u $ such that $ \delta(H_k) = \delta $ and the induced subetaaph of $ N(u) $ in $ H_k $ is not complete. The resulting graph $ H_k $ is a connected graph with maximum degree $ \Delta(G) = \Delta $ and maximum degree $ \delta(G) = \delta $. It can be checked that $ \gamma(H_k) = k+1 $ and $ \gamma_R(H_k) = k+2 = \frac{\Delta+2\delta}{\Delta+\delta}\gamma(G) $.

For example, if $ k = 2 $, $ \delta = 3 $ and $ \Delta = k\delta = 6 $, then the graph $ H_2 $ constructed by the above method is shown in Figure 1, where $ u_1 $ and $ u_2 $ are new vertices.

Figure 1.  An example to illustrate the construction of $ H_k $.

DownLoad: Full-Size Img PowerPoint

Furthermore, by Theorem 3, we can obtain a lower bound of the Roman domination number on regular graphs.

Corollary 4. Let $ G $ be an $ r $-regular graph, where $ r\geq 1 $. Then

Moreover, if the equality holds, then

Proof. Since $ G $ is $ r $-regular, we have $ \Delta(G) = \delta(G) = r $. By Theorem 3 we can obtain that this corollary is true.

For any integer $ n\geq 2 $, denote by $ G_{2n} $ the $ (2n-2) $-regular graph with $ 2n $ vertices, namely $ G_{2n} $ is the graph obtained from $ K_{2n} $ by deleting a perfect matching. It can be checked that $ \gamma(G_{2n}) = 2 $ and $ \gamma_R(G_{2n}) = 3 = \frac{3}{2}\gamma(G) $ for any $ n\geq 2 $. Hence, the bound in Corollary 4 is attained.

Note that $ \gamma_{R}(G)\leq2\gamma(G) $ for any graph $ G $; we can conclude the following result.

Corollary 5. Let $ G $ be an $ r $-regular graph, where $ r\geq 1 $. Then

3.   Relationship between Roman domination and Roman {2}-domination numbers

Chellali et al. ^[5] obtain the following bounds for the Roman {2}-domination number of a graph $ G $.

Lemma 6. (Chellali et al. ^[5]) For every graph $ G $, $ \gamma(G)\leq\gamma_{\{R2\}}(G)\leq\gamma_{R}(G)\leq2\gamma(G) $.

Lemma 7. (Chellali et al. ^[5]) If $ G $ is a connected graph of order $ n $ and maximum degree $ \Delta(G) = \Delta $, then

Theorem 8. For every graph $ G $, $ \gamma_{R}(G)\leq2\gamma_{\{R2\}}(G)-1 $. Moreover, for any integer $ k\geq2 $, there exists a graph $ I_k $ such that $ \gamma_{\{R2\}}(I_k) = k $ and $ \gamma_{R}(I_k) = 2k-1 $.

Proof. Let $ f = (V_0, V_1, V_2) $ be an $ \gamma_{\{R2\}} $-function of $ G $. Then $ \gamma_{\{R2\}}(G) = |V_1|+2|V_2| $ and $ \gamma_{R}(G)\leq 2|V_1|+2|V_2| $ since $ V_1\cup V_2 $ is a dominating set of $ G $. If $ |V_2|\geq 1 $, then $ \gamma_{R}(G)\leq 2|V_1|+2|V_2| = 2\gamma_{\{R2\}}(G)-2|V_2|\geq 2\gamma_{\{R2\}}(G)-2 $. If $ |V_2| = 0 $, then every vertex in $ V_0 $ is adjacent to at least two vertices in $ V_1 $. So for any vertex $ u\in V_1 $, $ f' = (V_0, \{u\}, V_1\setminus \{u\}) $ is an RDF of $ G $. Then we have $ \gamma_{R}(G)\leq 1+2|V_1\setminus \{u\}| = 2|V_1|-1 = 2\gamma_{\{R2\}}(G)-1 $.

For any integer $ k\geq2 $, let $ I_k $ be the graph obtained from $ K_k $ by replacing every edge of $ K_k $ with two paths of length 2. Then $ \Delta(I_k) = 2(k-1) $ and $ \delta(I_k) = 2 $. We first prove that $ \gamma_{\{R2\}}(I_k) = k $. Since $ V(I_k) = |V(K_k)|+2|E(K_k)| = k+2\cdot\frac{k(k-1)}{2} = k^2 $, by Lemma 7 we can obtain $ \gamma_{\{R2\}}(I_k)\geq\frac{2|V(I_k)|}{\Delta(I_k)+2} = \frac{2k^2}{2(k-1)+2} = k $. On the other hand, let $ f(x) = 1 $ for each $ x\in V(I_k) $ with $ d(x) = 2(k-1) $ and $ f(y) = 0 $ for each $ y\in V(I_k) $ with $ d(y) = 2 $. It can be seen that $ f $ is an R$ \{2\} $DF of $ I_k $ and $ w(f) = k $. Hence, $ \gamma_{\{R2\}}(I_k) = k $.

We now prove that $ \gamma_{R}(I_k) = 2k-1 $. Let $ g = \{V'_1, V'_2, V'_3\} $ be a $ \gamma_{R} $-function of $ I_k $ such that $ |V'_1| $ is minimum. For each 4-cycle $ C = v_1v_2v_3v_4v_1 $ of $ I_k $ with $ d(v_1) = d(v_3) = 2(k-1) $ and $ d(v_2) = d(v_4) = 2 $, we have $ w_g(C) = g(v_1)+g(v_2)+g(v_3)+g(v_4)\geq 2 $. If $ w_g(C) = 2 $, then by Lemma 2(iii) we have $ g(v_i)\in \{0, 2\} $ for any $ i\in\{1, 2, 3, 4\} $. Hence, one of $ v_1 $ and $ v_3 $ has value 2 and $ g(v_2) = g(v_4) = 0 $. If $ w_g(C) = 3 $, then by Lemma 2(i) we have $ \{g(v_1), g(v_3)\} = \{1, 2\} $ or $ \{g(v_2), g(v_4)\} = \{1, 2\} $. When $ \{g(v_2), g(v_4)\} = \{1, 2\} $, let $ \{g'(v_1), g'(v_2)\} = \{1, 2\} $, $ g'(v_2) = g'(v_4) = 0 $ and $ g'(x) = g(x) $ for any $ x\in V(I_k)\setminus \{v_1, v_2, v_3, v_4\} $. Then $ g' $ is also a $ \gamma_{R} $-function of $ I_k $. If $ w_g(C) = 4 $, then exchange the values on $ C $ such that $ v_1, v_3 $ have value 2 and $ v_2, v_4 $ have value 0. So we obtain that $ I_k $ has a $ \gamma_{R} $-function $ h $ such that $ h(y) = 0 $ for any $ y\in V(I_k) $ with degree 2. Note that any two vertices of $ I_k $ with degree $ 2(k-1) $ belongs to a 4-cycle considered above; we can obtain that there is exactly one vertex $ z $ of $ I_k $ with degree $ 2(k-1) $ such that $ h(z) = 1 $. Hence, $ \gamma_{R}(I_k) = w(h) = 2k-1 $.

Note that the graph $ I_k $ constructed in Theorem 8 satisfies that $ \gamma(I_k) = k = \gamma_{\{R2\}}(I_k) $. By Theorem 8, it suffices to prove that $ \gamma(I_k) = k $. Let $ A = \{v: v\in V(I_k), d(v) = 2(k-1)\} $ and $ B = V(I_k)\setminus A $. We will prove that $ I_k $ has a $ \gamma $-set containing no vertex of $ B $. Let $ D $ be a $ \gamma $-set of $ I_k $. If $ D $ contains a vertex $ u\in B $. Since the degree of $ u $ is 2, let $ u_1 $ and $ u_2 $ be two neighbors of $ u $ in $ I_k $. Then $ d(u_1) = d(u_2) = 2(k-1) $ and, by the construction of $ I_k $, $ u_1 $ and $ u_2 $ have two common neighbors $ u, u' $ with degree 2. Hence, at least one of $ u', u_1 $, and $ u_2 $ belongs to $ D $. Let $ D' = (D\setminus\{u, u'\})\cup\{u_1, u_2\} $. Then $ D' $ is also a $ \gamma $-set of $ I_k $. Hence, we can obtain a $ \gamma $-set of $ I_k $ containing no vertex of $ B $ by performing the above operation for each vertex $ v\in D\cap B $. So $ A $ is a $ \gamma $-set of $ I_k $ and $ \gamma(I_k) = |A| = k $.

By Lemma 6 and Theorem 8, we can obtain the following corollary.

Corollary 9. For every graph $ G $, $ \gamma_{\{R2\}}(G)\leq\gamma_{R}(G)\leq2\gamma_{\{R2\}}(G)-1 $.

Theorem 10. For every graph $ G $, $ \gamma_{R}(G)\leq\gamma(G)+\gamma_{\{R2\}}(G)-1 $.

Proof. By Lemma 6 we can obtain that $ \gamma_{R}(G)\leq2\gamma(G)\leq \gamma(G)+\gamma_{\{R2\}}(G) $. If the equality holds, then $ \gamma_{R}(G) = 2\gamma(G) $ and $ \gamma(G) = \gamma_{\{R2\}}(G) $. So $ \gamma_{R}(G) = 2\gamma_{\{R2\}}(G) $, which contradicts Theorem 8. Hence, we have $ \gamma_{R}(G)\leq\gamma(G)+\gamma_{\{R2\}}(G)-1 $.

4.   Conclusions

In this paper, we prove that $ \gamma_{R}(G)\geq\frac{\Delta+2\delta}{\Delta+\delta}\gamma(G) $ for any nontrivial connected graph $ G $ with maximum degree $ \Delta $ and minimum degree $ \delta $, which improves a result obtained by Chellali et al. ^[4]. As a corollary, we obtain that $ \frac{3}{2}\gamma(G)\leq\gamma_{R}(G)\leq 2\gamma(G) $ for any nontrivial regular graph $ G $. Moreover, we prove that $ \gamma_{R}(G)\leq2\gamma_{\{R2\}}(G)-1 $ for every graph $ G $ and the bound is achieved. Although the bounds in Theorem 3 and Theorem 8 are achieved, characterizing the graphs that satisfy the equalities remain a challenge for further work.

Acknowledgments

The author thanks anonymous referees sincerely for their helpful suggestions to improve this work. This work was supported by the National Natural Science Foundation of China (No.61802158) and Natural Science Foundation of Gansu Province (20JR10RA605).

Conflict of interest

The author declares that they have no conflict of interest.