SIAM J. DISCRETE MATH.
Vol. 26, No. 1, pp. 193–205
ROMAN DOMINATION ON 2-CONNECTED GRAPHS∗
CHUN-HUNG LIU†
AND GERARD J. CHANG‡
Abstract. A Roman dominating function of a graph G is a function f: V (G) → {0, 1, 2} such that whenever f(v) = 0, there exists a vertex u adjacent to v such that f(u) = 2. The weight of f is w(f) =  . The Roman domination number of G is the minimum weight of a Roman dominating function of G Chambers,Kinnersley, Prince, and West [SIAM J. Discrete Math.,23 (2009), pp. 1575–1586] conjectured that ≤ [2n/3] for any 2-connected graph G of n vertices.This paper gives counterexamples to the conjecture and proves that≤ max{[2n/3], 23n/34}for any 2-connected graph G of n vertices. We also characterize 2-connected graphs G for which = 23n/34 when 23n/34 > [2n/3].
Key words. domination, Roman domination, 2-connected graph
AMS. subject classifications. 05C69, 05C35
DOI. 10.1137/080733085
1. Introduction. Articles by ReVelle [14, 15] in the Johns Hopkins Magazine suggested a new variation of domination called Roman domination; see also [16] for an integer programming formulation of the problem. Since then, there have been several articles on Roman domination and its variations [1, 2, 3, 4, 5, 7, 8, 9, 10,11, 13, 17, 18, 19]. Emperor Constantine imposed the requirement that an army or legion could be sent from its home to defend a neighboring location only if there was a second army which would stay and protect the home. Thus, there are two types of armies, stationary and traveling. Each vertex (city) that has no army must have a neighboring vertex with a traveling army. Stationary armies then dominate their own vertices; a vertex with two armies is dominated by its stationary army, and its open neighborhood is dominated by the traveling army.
values翻译
  In this paper, we consider (simple) graphs and loopless multigraphs G with vert ex set V (G) and edge set E(G). The degree of a vertex v∈V (G) is the number of edges incident to v. Note that the number of neighbors of v may be less than degGv in a loopless multigraph. A Roman dominating function of a graph G is a function  f:
V(G) → {0, 1, 2} such that whenever f(v) = 0, there exists a vertex u adjacent to v such that f(u) = 2. The weight of f, denoted by w(f), is defined as.For any subgraph H of G, let w(f,H) =. The Roman dominationnumber of G is the minimum weight of a Roman dominating function.
Among the papers mentioned above, we are most interested in the one by Chambers et al. [2] in which extremal problems of Roman domination are discussed. In particular, they gave sharp bounds for graphs with minimum degree 1 or 2 and boundsof  +  and . After settling some special cases, they gave the following conjecture in an earlier version of the paper [2].Conjecture (Chambers et al. [2]). For any 2-connected graph G of n vertices, ≤ [2n/3]。
  This paper proves that  ≤ max{[2n/3], 23n/34} for any 2-connected graph G of n vertices.
Notice that 23n/34 is larger than 2n/3 by n/102. We also characterize 2-connected graphs G with  = 23n/34 when 23n/34 > [2n/3]. This was in fact suspected by West through a private communication and proved after some discussions with him.
2. Counterexamples to the conjecture. In this section, we give counterexamples to the conjecture by Chambers et al. [2].
The explosion graph of a loopless multigraph G is the graph with vertex set V() = V (G) ∪ {, , , ,  : e = xy ∈ E(G)} and edge set E) ={x, y , ,  , ,, e : e = xy ∈ E(G)}; see Figure 1. Notice that {, , ,  } induces a 5-cycle in , denoted by Ce. We call , ,  the inner vertices of Ce and of . Note that even if G has parallel edges, its explosion graph ,is a simple grap
Theorem 1. There are infinitely many 2-connected graphs with Roman domination number at least 23n/34, where n is the number of vertices in the graph.
Proof. Consider k graphs ,, . . . , , each isomorphic to , and their explosiongraphs ,, . . . , . Let G be a 2-connected graph obtained from the disjoint union of these explosion graphs’s
by adding suitable edges between vertices of the original graphs s; i.e., these added edges and the s form a 2-connected graph. Then, G has n = 34k vertices.
We claim that  ≥ 23n/34 = 23k. Suppose to the contrary that  <23k. Choose an optimal Roman dominating function f of G. Since  =w(f) < 23k, there is some with w(f,) < 23.
Notice that for any edge xy in , no matter what the values of f(x) and f(y) are, it is always the case that w(f,) ≥ 3. Furthermore, if f(x) ≤ 1 and f(y) ≤ 1, then in fact w(f,) ≥ 4. Suppose  has r vertices v with f(v) ≤ 1, where 0 ≤ r ≤ 4.There are then（）edges x y in with w(f,) ≥ 4. Thus

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。