数学外文+中文翻译.docx

1、SIAM J. DISCRETE MATH.Vol. 26, No. 1, pp. 193205ROMAN DOMINATION ON 2-CONNECTED GRAPHSCHUN-HUNG LIUAND GERARD J. CHANGAbstract. 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

2、 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. 15751586 conjectured that 2n/3 for any 2-connected graph G of n vertices.This paper gives counterexamples to the conje

3、cture and proves that max2n/3, 23n/34for 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 graphAMS. subject classifications. 05C69, 05C35DOI. 10.1137/0807330851. Introduction. Art

4、icles 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,

5、 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) th

6、at 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. In this paper, we consider (simple) graphs and loopless

7、 multigraphs G with vert ex set V (G) and edge set E(G). The degree of a vertex vV (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 whenev

8、er 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

9、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.Co

10、njecture (Chambers et al. 2). For any 2-connected graph G of n vertices, 2n/3。 This paper proves that max2n/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

11、 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)

12、, , , , : 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 grapTheorem 1. There are infinitely many 2

13、-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 graphss by a

14、dding 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 wi

15、th w(f,) w(f,) r 0 + (4 r)2 + 6 3 +（）or, equivalently, 2r 3 +（）,which is impossible as 0 r 4.The lower bound 23n/34 in the theorem above is in fact the exact value for the given graph G. This will be seen from the following theorem, whose proof employs a method that is useful in the entire paper.For

16、 technical reasons, we often consider three Roman dominating functions , , and . We use to denote the 3-tuple (, ,), and (v) for ( (v), (v), (v). The weight of is w() =. Note that w( ) w()/3 for some j. A vertex v is -strong if (v) = 2 for some j.Theorem 2. If is the explosion graph of a loopless mu

17、ltigraph G without isolated vertices andhas vertices, then has a 3-tuple of Roman dominating functions such that w() 69/34 and every noninner vertex is -strong. Furthermore, if such satisfies w() = 69/34, then G is a disjoint union of s.Proof. If G has n vertices and m edges, then = n + 5m. We shall

18、 construct by first assigning values 0, 1, or 2 to the vertices in G. For this purpose, we order the vertices of G into , , . . . , and let be the subgraph of G induced by , . . . , as follows.Notice that = G. Starting from i = n, do the following loop: if Gi has a vertex of degree not equal to 3 or

19、 a vertex of degree 3 that has at most two neighbors, then choose it as vi; otherwise choose a vertex of degree 3 as vi and its three neighbors as , , . For the former case, let = and then replace i by i1 to repeat the loop; for the latter case, let = for k = i, i 1, i 2, i 3 and then replace i by i

20、 4 to repeat the loopEvery edge of G serves as a “back edge” of some , i.e., with i k. Hence, m = 。Once () has been defined for k 2n/3 and G contains no spanning subgraph isomorphic to the explosion graph of a disjoint union of K4s, then max2n/3, 23n/34, and any 2-connected graph of order with + |E(

21、)| n+ |E(G)| satisfies R() max2n/3, 23/34. In particular, G is a minimally 2-connected graph. According to Lemma 4, we have the following claim.Claim 1. G does not have a cycle with a chord.Lemma 4 (Dirac 6, Plummer 12). A 2-connected graph is minimally 2- connected if and only if every cycle is an

22、induced cycle.A cycle is pendent if it has no chords and all of its vertices except exactly two nonadjacent vertices are of degree 2.Claim 2. Any two pendent 5-cycles in G are vertex-disjointProof. Suppose to the contrary that G has two pendent 5-cycles and that are not vertex-disjoint. Let = and ,

23、be the two vertices of degree at least 3 for i = 1, 2, where = and possibly = . We now consider the graph obtained from the subgraph of G induced by V (G) : i = 1, 2, j = 2, 4, 5 by adding edges and . It is clear that is a 2- connected graph with = n6 vertices and |E()| |E(G)|. By the minimality of

24、G, we have R() max2/3, 23/34. Choose a Roman dominating function of with w() = R(). Define function g on V (G) by g(v) =(v) for all vV (C1 C2) andfor i = 1, 2. Then g is a Roman dominating function of G with w(g) w() + 4.This givesR() max2n/3, 23n/34, a contradiction to the choice of G.Notice that e

25、ach pendent 5-cycle in G can be extended to an explosion graph of But, putting them together is not necessarily an explosion graph, as a vertex in some pendent 5-cycle may possibly be the vertex of an explosion graph of K2 which is extended from another pendent 5-cycle. However, the following lemma

26、will produce an explosion graph that overlaps all pendent 5-cycles in G by choosing S as the empty set.Lemma 5. Let H be a graph in which any two pendent 5-cycles are vertex-disjoint, and let S be a subset of V (H). If every pendent 5-cycle C of H is adjacent to at least two vertices in HV (C), then

27、 H has a subgraph L isomorphic to the explosion graph of a loopless multigraph without isolated vertices such that no pendent 5-cycles in H are vertex-disjoint from S V (L), but every pendent 5-cycle in L is vertex-disjoint from S.Proof. Suppose that H has k pendent 5-cycles , , . . . , which are ve

28、rtexdisjoint from S, where and are the two vertices of degree at least 3 of for all i. We shall prove the lemma by induction on k. The lemma is clear for k = 0. Suppose now that k 1. Construct an auxiliary digraph F with V (F) = and E(F) = E(H): has degree 3 in H. Then each has indegree 1, and = 1 i

29、mplies the outdegree 1. Hence, there is at least an index r with 1 and 1.For otherwise, for each i, either 2 or 2, and so either =0 or degDvi,3 = 0. The former implies that |E(F)| = 2k, while the latter implies that |E(F)| = k and for all i 2+2 and w(,L) = 69/34, then L has a spanning subgraph isomo

30、rphic to the explosion graph of a disjoint union of . Note that L is an induced subgraph of G, as adding edges preserves condition (M). We shall derive a contradiction from the fact that GL. It is possible that L is empty, as G may contain no pendent 5-cycle. In that case, we apply Lemma 6 to get a

31、nonempty LLemma 6. If t 3, then the t-cycle Ct has a 3-tupleof Roman dominating functions in which all vertices are -strong and w() 2t when t is a multiple of 3 and w() 2t + 2 otherwiseProof. Suppose V () = , , . . . , and E(Ct) = , , . . . , ,. For the case when t = 3p, the following is as desired:

32、 (v3i+1) = (2, 0, 0),(v3i+2) = (0, 2, 0), and(v3i+3) = (0, 0, 2) for all i. For the case when t = 3p + 1(respectively, t = 3p + 2), the above with the following modification is as desired: (v1) = (2, 0, 1) and (vt) = (2, 1, 0) (respectively, (v1) = (2, 0, 2).Claim 3. L is not emptyProof. If G contai

33、ns pendent 5-cycles, then the claim follows from Lemma 5 and Theorem 2; otherwise the claim follows from Lemma 6 and the fact that a 2-connectedgraph has a cycleTo establish more properties for L, we also need the following lemmaLemma 7. Suppose H has a 3-tuple of Roman dominating functions for whic

34、h u and v are -strong, say (u) = 2 and (v) = 2. If is obtained from H by adding a disjoint path P = . . . with t 1 and two edges u and V, thencan be extended to such that w(,P) = 2t and is-strong for 1 i t.Furthermore, and are also -strong if t 2 (mod 3) with j k or t 2 (mod3) with j = k.Proof. We shall define as () = (2, 0, 0), () = (0, 2, 0), and () =(0, 0, 2)