IMFM Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia Preprint series Vol. 49 (2011), 1165 ISSN 2232-2094 ROMAN DOMINATION NUMBER OF THE CARTESIAN PRODUCTS OF PATHS AND CYCLES Polona Pavlic Janez Zerovnik Ljubljana, November 25, 2011 Roman domination number of the Cartesian products ¡^ of paths and cycles $H ^ Polona Pavlic 10 vD CM s m m CO Institute of Mathematics, Physics and Mechanics, (D Jadranska 19, 1000 Ljubljana, Slovenia > q polona.pavlic@imfm.si Janez Zerovnik LO Faculty of Mechanical Engineering, University of Ljubljana, Askerceva 6, Ljubljana, Slovenia and Institute of Mathematics, Physics and Mechanics, ^ Jadranska 19, 1000 Ljubljana, Slovenia ^ janez.zerovnik@imfm.uni-lj.si ^ November 16, 2011 O CM CM CO CM Abstract 2010 Mathematical Subject Classification: 05C25, 05C69, 05C85, 68R10 Roman domination is a historically inspired variety of general domination such that every vertex is labeled with labels from {0,1, 2}. Roman domination number is the smallest of the sums of labels fulfilling condition that every vertex, labeled 0, has a neighbor, labeled 2. Using algebraic approach we give O(C) time algorithm for computing Roman domination number of special classes of polygraphs (rota-and fasciagraphs). By implementing the algorithm we give formulas for Roman pT f domination number of the Cartesian products of paths and cycles PnDPk, PnnCk for k < 8 and n € N and for CnoPk and CnoCk for k < 5, n € N. We also give a list of Roman graphs among investigated families. CO CD 1 Introduction ■ i CD Domination and its variations have been intensively studied and its algorithmic aspects have been widely investigated [15, 16]. It is well known that the problem of determining domination number of arbitrary graphs is NP-complete [15]. It is therefore interesting to Jh Q p THE ELECTRONIC JOURNAL OF COMBINATORICS 16 (2009), #R00 CD lO csr u o ¡5 o I consider algorithms for some classes of graphs, including grid graphs. Exact domination numbers of the Cartesian products of paths PnOPk with fixed k was established in [1, 5, O 7, 13, 14], of the Cartesian product of cycles in [9, 19, 30] and of the Cartesian products ^ of cycles and paths in [25]. A general O(log n) algorithm based on path algebra approach, which can be used to compute domination number of PnmPk for a fixed k, has been proposed in [20]. The algorithm of [20] can in most cases, including the computation of distance based invariants [18] and the domination numbers [31], be turned into a constant time algorithm, i.e. the algorithm can find closed formulas for arbitrary n. The existence ,-Q of an algorithm that provides closed formulas for domination numbers on grid graphs has ^ been observed or claimed also in [11, 23]. ^ An interesting variety of the graph domination that is popular because of its historical ^ motivation [26, 29] is called Roman domination. The history of the problem goes back to the 4th century, when Emperor Constantine tried to secure the Roman Empire by placing armies in the cities in a way that the area would be secured with minimum possible number of armies, some of which could also be sent to defend neighboring cities VQ without leaving the "home" city unsecured. While the problem is still of interest in i—I military operations research [2] it also has obvious applications anywhere when a time 1—1 critical service is supposed to be provided with certain backup. (For example, firemen brigade should never send all cars to answer the first emergency call.) Roman domination is a variety of the general domination such that different types of guards are used. Every vertex of a graph must be labeled with numbers from {0,1, 2} so that every vertex labeled ^ 0 has a neighbor labeled 2. Roman domination number of a graph is the smallest of the ^ sums of labels, such that they fulfill the above condition. Formal definition was proposed O in [6] and is recalled in Section 2. As the problem of determining Roman domination number of a graph is NP-complete [8], it is interesting to determine Roman domination number of some classes of graphs [6, 12, 17, 21, 22, 27, 28]. Also Vizing's-like conjecture for Roman domination [33] and CM some properties of YR-functions [4, 10, 24] were studied. One of the open problems posed ^ in the first article on this variety of domination [6] was to determine exact Roman dom-^ ination number for arbitrary grid graph. Roman domination numbers for PnDPk for CO k £ {1, 2, 3, 4} and n £ N have been computed in [6, 8]. An algorithm for computing XTl Roman domination number of grid graphs for a fixed k in linear time was also presented in [8]. Here we use path algebra approach to design an O(log n) algorithm for Roman domination numbers of grid graphs and show how it can be turned into a constant time p^ algorithm that provides closed formulas for Roman domination numbers of grid graphs. More precisely, the algorithm's time complexity is independent of n and has superpoly-^ nomial time complexity in terms of k. We use the algorithm to find formulas for Roman domination number of PnDPk and PnnCk for k < 8 and n £ N and for CnnPk and Cn DCk CO for k < 5 and n £ N. In the rest of this paper we first summarize the background for the main algorithm. Section 2 is dedicated to the concept of polygraphs, which has been widely used in chemi-^ cal graph theory and elsewhere. In Section 3 we summarize a general algorithm for solving different problems on polygraphs, which was proposed in [20]. The algorithm for comput- CD •tH $H CD Jh Q p THE ELECTRONIC JOURNAL OF COMBINATORICS 16 (2009), #R00 CD $H lO vD ing Roman domination number for faciagraphs and rotagraphs is presented in Section 4. Section 5 then summarizes some results obtained by implementing the algorithm. Roman graphs (i.e. graphs, satisfying 'Jr(G) = 27(G)) among graphs we investigate are listed in Section 6. Finally, constructions for 7^- functions of graphs are presented. IO 2 Preliminaries J-H We consider finite undirected and directed graphs. A graph will always mean an undirected graph, a digraph will stand for a directed graph. An edge in an undirected graph will be denoted uv while in directed graph, an arc between vertices u and v will be denoted (u, v). Pn will stand for a path on n vertices and Cn for a cycle on n vertices. For a graph G = (V,E), a set D is a dominating set if every vertex in V \ D is adjacent to a vertex in D. The domination number 7(G) is the minimum cardinality of a dominating set of G. A dominating set of cardinality 7(G) is called a minimum dominating set, or shortly a 7-set. Roman domination has been formally defined in [6] as follows: For a graph G = (V, E), let f : V —> {0,1,2} and let (Vo, Vi, V2) be the ordered partition of V induced by /, where Vi = {v G V(G) \ f(v) = ?'}. Let \Vi\ = iii for i = 0,1,2. Note that there exists a 1-1 correspondence between the functions / : V —> {0,1,2} and ordered partitions {V0,VUV2) of V. Thus, we will write / = (V0,V1,V2). A function / = (Vb, VUV2) is a Roman dominating function (RDF) if V2 y Vo, in other words, if the set V2 dominates the set Vo. The weight of / is defined as: «'(/) = f(v) = ni + 2/7.2. vev csr 00 The Roman domination number, 7r(G), equals the minimum weight of an RDF of G. We will also say that a function / = (Vo, V\, V2) is a 7ij-function, if it is an RDF and w(f) = 7b(G). Obviously, 7(G) < 7_r(G) < 27(G). Only graphs that satisfy 7_r(G) = 7(G) are edgeless graphs and a graph G is called a Roman graph if Jr(G) = 27(G). Finding classes of Roman graphs was one of the open problems posed in [6]. For instance, among paths, graphs Psk and P$k+2 are Roman graphs since 7r (P3fc+i) = 2A: + 1 < 27 (^3^+1) = '2k + 2. The difference between 7r and 27 can be arbitrary large, for example on the family of subdivided stars. Subdivided star is obtained from the star Sn+1 = by subdivision of each edge. We have 7#(A'iin) = 2 + n < 27(A'l n) = 2n. Construction of minimum dominating set and 7^-function for Ki 5 can be seen on Figure 1 where full circs represent vertices in the domination set on the left side and vertices of weight 1 in 7ij-function on the right side. Vertex of weight 2 in the 7ij-function is presented with double circ. The Cartesian product of graphs G and H, denoted GOH, is a graph with vertex set V(G) x V(H) and two vertices (g, h.) and ( o £ 10 VD O Ö o CM CM 00 CM CM £ m m Let Gi,..., Gn be arbitrary mutually disjoint graphs and Xi,..., Xn a sequence of sets of edges such that an edge of Xj joins a vertex of V(Gi) with a vertex of V(Gi+1). For convenience we also set Go = Gn, Gn+1 = G1 and X0 = Xn. This in particular means that edges in Xn join vertices of Gn with vertices of G1. A polygraph Qn = Qn(G1,... Gn; X1;... Xn) over monographs G1,..., Gn is defined in the following way: V (Qn) = V (G1) U ... U V (Gn), E(Qn) = E(G1) U X1 U ... U E(Gn) U Xn. For a polygraph Qn and for i = 1,..., n we also define Di = {u G V(Gj) | 3v G Gj+1 : uv G Xj}, Ri = {u G V(Gj+1) | 3v G Gj : uv G Xj}. In general, Rj H Dj+1 does not have to be empty. If all graphs Gj are isomorphic to a fixed graph G and all sets Xj are equal, then we call such a graph rotagraph and denote it wn(G; X). A rotagraph without edges between the first and the last copy of G (formally, Xn = 0) is fasciagraph, ^n(G; X). In rotagraph as well as in fasciagraph, all sets Dj and Rj are equal. We will denote those two sets with D and R, respectively. Observe that Cartesian products of paths PnmPfc are examples of fasciagraphs and that Cartesian products of cycles CnnCk are examples of rotagraphs. Graphs PnnCk can be treated as fasciagraphs or as rotagraphs. m CD CD m 3 Path algebras and the algorithm Let us now summarize a general framework for solving different problems on the class of fasciagraphs and rotagraphs, which was proposed in [20] and also used in [31]: A semiring P = (P, ®, o, e®, e°) is a set P on which two binary operations, © and o are defined such that: 1. (P is a commutative monoid with e® as a unit; U a CD U ¡5 2. (P, o) is a monoid with e° as a unit; 3. o is left- and right-distributive over ©; 4. Vx e P,x O e® = e® = e® O x. m An idempotent semiring is called a path algebra. It is easy to see that a semiring is a path algebra if and only if e° © e° = e° holds for e°, the unit of the monoid (P, o). An important example of a path algebra for our work is V\ = (No U {oo}, min, +, oo, 0). Here No denotes the set of nonnegative integers and N the set of positive integers. For more examples of path algebras we refer to [3]. Let V = (P, ©, o, e®, e°) be a path algebra and let M.n(V) be the set of all n x n matrices over P. Let A,Be M.n(V) and define operations © and o in the usual way: (A © — Aij © B v n (A oB)ij = 0 .1./, :: k=1 1—1 M.n(P) equipped with above operations is a path algebra with the zero and the unit matrix as units of semiring. In our example V\ = (No U {oo},min, +, oo,0), all elements of the zero matrix are oo, the unit of the monoid (P, min), and the unit matrix is a diagonal matrix with diagonal elements equal to e° = 0 and all other elements equal to e® = oo. Let V be a path algebra and let G be a labeled digraph, that is a digraph together with a labeling function £ which assigns to every arc of G an element of P. Let V(G) = {i'i, V'2,..., vn}. The labeling £ of G can be extended to paths in the following way: For a path Q = (vio, vh)(vil, vi2)... (v»fc_1, of G let £(Q) = £ (vio, vh) o £ (v^v^) o ... o £ (vi^v^) Let be the set of all paths of order k from Vi to Vj in G and let A(G) be the matrix defined by: r • • ~ < (^Vi'' Vj"> is an ar° G %J le®; otherwise It is well-known (see for example [3]) that (MG)k)tJ = © mV Let un(G; X) be a rotagraph and 4'n(G] X) a fasciagraph. Set U = Di U Ri = D U R and let N = 2^. Define a labeled digraph Q = Q(G;X) as follows: The vertex set of Q is formed by the subsets of U which will be denoted by Vi. An arc joins a subset Vi with a subset Vj if Vi is not in a "conflict" with Vj. Here a conflict of Vi with Vj means J-H CD that using V and Vj as a part of a solution in consecutive copies of G would violate the problem assumption. For instance, if we look for a domination number of a graph, such a conflict would be a nonempty intersection between sets V and Vj, or if we look for an independence number of a graph, such a conflict would be an edge between sets V and Vj. Let finally I : E(G) —> P be a labeling of G where P is a path algebra on the set P. The general scheme for the algorithm as proposed in [20] is: CM 10 CM $H ^ Algorithm 1 [20] - 1. Select the appropriate path algebra P = (P, ©, o, e®, e°). JD 2. Determine an appropriate labeling I of a graph G(G; X). o £ lO VD 3. In ) calculate A (G)n. 4. Among admissible coefficients of A (G)n select one which optimizes the corresponding goal function. It is well known that, in general, Step 3 of the algorithm can be implemented to run in O(log n) time. However, computing the powers of A (G)n = An in O(C) time is possible using special structure of the matrices in some cases, including the distance based invariants [18], the domination numbers [31], and others [32]. Here we prove that A (G)n = An can be computed in O(C) time for Roman domination number (see Section O 4). CM i 4 Roman domination number of fasciagraphs and ro-CM tagraphs Let wn(G; X) be a rotagraph and ^n(G; X) a fasciagraph as defined above. Set U = Di U Ri = D U R. (Keep in mind that Di C Gi and R C Gi+i, but since R = R and CO Di = D for all i, we can write U = Di U Ri = D U R). A labeled digraph G = G(G; X) is 1—1 a graph with vertex set: V(G) = {(Vi,Wi) | Vi,Wi c u,Vi n Wi = 0} For convenience we sometimes refer to a vertex of G shortly by vi = (Vi, Wi). In particular, ^ v0 = (V0, W0) stands for (0, 0). ^ Let vi,vj G V(G) and consider for a moment ^(G;X). Let Vi U Wi C D1 U R1 ^ and Vj U Wj C D2 U R2. Let (G; X) be the weight of a YR-function of a graph G2 \ (((Vi U Wi) n Ri) U (D2 n (Vj U Wj))), such that Vi U Vj C V' and Wi U Wj C W', where (V0', V', W') is an RDF of a graph G2. For consistency, we introduce an arc between H p THE ELECTRONIC JOURNAL OF COMBINATORICS 16 (2009), #R00 CD Gi Go G, CSI «n lO CSI u CD S CD > o ¡5 «n LO vD 0 Ö «n o CSI 1 CSI 00 CSI CSI ¡5 CO CO CO CD ■ I u CD CO u Oh CD U Figure 2: ^/»3(G;X) with the above notation and i? n Wi n Vj n D ). Set vertices Vi and Vj only if R fl Vi fl Wj fl D - e(vi,vj) = \RnVi\ + 2\RnWi\ + \Vj nD\ + 2\Wj nD\ - -\RnVinVjnD\-2\RnWin Wj nD\+ 7^.(G; X). (1) Then we have an algorithm which computes Roman domination number of rotagraphs and fasciagraphs: Algorithm 2 1. For a path algebra select V = (No U {oo},min, +, oo, 0). 2. Label Q = Q(G]X) as defined above. 3. In MiV) calculate A (Q)'2. 4. Let lR (V'„(G; X)) = (A (G)n)00 and lR (w„(G; X)) = min, (A Theorem 4.1 The Algorithm 2 correctly computes Roman domination number of rotagraphs and fasciagraphs: lR(MG-,X)) = (A(g)n)00 (2) -yR(u>n(G;X)) = mm(A(g)n)ii (3) % in 0(log ??.) time. Proof. Let Gi and G2 be arbitrary graphs, Xx a set of edges between vertices of Gi and G2 and let il2(Gi, G2; 0) be a polygraph. Let also V = (N0 U {oo}, min, +, oo, 0) be a path algebra and let Q' be a labeled digraph for Q2 defined as above. Then, by the definition of labeling, we have 7i?(n2(G1,G2;X1, i [A(G1) + A(G2)] oo min {/{(). rA 5 • /ir,.())} Vk&V(Q) CM •n LO CM u CD ¡5 •n LO vD Let G i = G, X\ = X and G2 = V'n-i (C; X). Then (2) follows by induction. For (3), similarly, consider £12(Gi, G2, X\, X2) and let G\ = G, X\ = X2 = X and G2 = V'„-i(G;X). Time complexity of the algorithm was already discussed for general case in Section 3. □ As mentioned before we prove that calculating powers of matrices A (Q)n = An (and therefore implementing the algorithm) is possible in 0(C) time based on the following lemma: g Lemma 4.2 Let k = \V(G(G]X))\ and I< = \V(G)\. Then there is an index q < (AI< + 2)fc" such that Dq = Dp + C for some index p < q and some constant matrix C. Let P = q — p. Then for every r > p and every s > 0 we have Af-\-sP — Ap sG. Proof. First observe that for any / > 1, the difference between any pair of entries of Ai, both different from oo, is bounded by AK: Assume (Ai)ij ^ oo. Then (Ai)ij = 1r ((V(Gi) \ (Vi U Wi)) U V(G2) U ... U V(G/_i) U {V{Gi) \ (Vj U Wj))) <7 r{MG;X)). Since Vt n Wt = 0 and Vj n Wj = % it follows that |R n V-| + 2 |i? n Wt| + \Vj n D\ + 2 |Wj DD\< A\V(G)\. According to (1) we have Ov^Vj) < A\V(G) \ + YRij = MV(G)\ + (At)l3 > ¿(Vi, Vj) - A\V(G)\ > lR (UG- X)) - A\V(G)\. Therefore 7r(MG;X)) ~ A\V(G)\ < (^)y < 7RMG-,X)). For I > 1, let A/ = min{(A/)y} and let A[ = Ai — (A/)J, where J is the matrix with all entries equal to 0 (recall that we are still in the path algebra V = (NoU{oo}, min, +, oo, 0)). Since the difference between any two elements of Ai, different from oo, cannot be greater than AK, the entries of A[ can have only values 0,1,..., AK, oo. Hence there are indices p < q < (AK + 2)fc" such that A' = A'. This proves the first part of the proposition. The equality Ar+Sp = Ar + sC follows from the fact that for arbitrary matrices D, E and a constant matrix C we have (D © C) o E = D o E © C. This can easily be seen by computing the values of ¿j-th entries of both sides of the equality: •s ((D © C) o E)%] = min{((D)ik + C) + (E)kj} = min{(D)ik + (E)kj} + C k k (D o E © Oij = min{(D)ik + (E)kj} + (C% = min{(D)ik + (E)kj} + C. k k □ THE ELECTRONIC JOURNAL OF COMBINATORICS 16 (2009), #R00 CD Hence, if we assume that the size of G is a given constant (and n is a variable), then the algorithm will run in constant time. But it is important to emphasize that the algorithm is useful for practical purposes only if the number of vertices of the monograph G is relatively small, since the time complexity is in general exponential in the number of vertices of the monograph G. 5 Products of paths and cycles Our aim is to calculate Roman domination number for graphs PnnPk, PnUCkl CnOPk and CnOCk for some fixed k. Since these graphs are isomorphic to special classes of fasciagraphs and rotagraphs (i.e. fasciagraphs and rotagraphs where G = Pk or G = Ck and where X is a matching between two copies of G), Lemma 4.2 implies a constant time algorithm for computing their Roman domination numbers, but its straightforward application is not useful in our case since indices q are huge. Because with increasing k, matrices A(G)n become bigger and bigger, we also omitted straightforward implementation of Algorithm 2. Instead of calculating whole matrices A(G)n, we calculated only those rows which are important for the result and checked the difference of the new row against the previously stored rows until a constant difference was detected. This yields a correct result because of the next lemma, adaptation of Lemma from [32], lO vO ¡5 CO CO Lemma 5.1 Assume that the j-th row of An+P and An differ for a constant, + C for i- Then miiij a[™+P^ = miiij + G. o Proof. Let a^^ = niin» and assume that there exists I ^ k such that a^ > aff. It follows that which contradicts the minimality of ajk . □ By implementation we got formulas presented in the following subsections. For each case also constructions of 7^-functions are presented. In every figure that follows we only emphasized vertices of V\ and V2 of a 7^-function of a depicted graph in a way that a single full circ represents a vertex of V\ and a double circ represents a vertex of V2. 5.1 7R(PnnPk) for k G {5,6,7,8} Roman domination number of grid graphs was studied in [6, 8] and the following results have been established: CO CD ■ i-H J-H CD CO J-H THE ELECTRONIC JOURNAL OF COMBINATORICS 16 (2009), #R00 CD J-H o CM «n LO CM u CD a CD > o ¡5 «n LO vD 2 n 1R (Pn) = 1R (Cn) In (PnOP2) = n + 1 LxJ+2; if n E {4A: + 3 | fc G N U {0}} ■yR{PnnPs) lR{Pnnp4) +1; otherwise 2n+l; if n E {1,2,3, 5,6} 2 n: otherwise No formulas were given for k > 4. However, the author also proposed an algorithm for computing 7r (PnnPk) for fixed k in 0(n) time. By implementing Algorithm 2 as already discussed above, we obtained formulas given below. We also looked for the constructions for every n. Roman dominating sets of weight 7r are depicted for every case on Figures 3 to 6. 0 Ö «n o CM 1 CM 00 CM CM ¡5 CO CO CO CD ■ i-H u CD CO lR(Pnap5) lR(PnOP6) lR(Pnap7) lR(Pnap8) 8; if n = 3 im- F2 otherwise im- F2 if n < 5 or n E {5k, 5k + 3, 5A: + 4 | k E N} im- 1-3 otherwise fm- F2 if n E {1,2,4,7, | k E N} im- 1-3 otherwise '9; if n = 2 16; if n = 4 UfJ- f 4 if n E {5k + 3 | k E N} f 3 otherwise Roman domination numbers for small grids are presented in Table 1. 5.2 7R{PknCn) for k G {3, 4, 5, 6, 7, 8} In the literature we found no formulas for Roman domination numbers in these cases. Our formulas are given below. Constructions for each case are depicted on Figures 7 to 12. U Oh CD U Table 1: Roman domination number of some PnOPk. o CM «n LO CM u CD a CD > o ¡5 «n LO vD 0 Ö «n o CM 1 CM 00 CM CM ¡5 CO CO CO CD ■ i-H u CD CO k \ n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 1 2 2 3 4 4 5 6 6 7 8 8 9 10 10 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 3 6 7 8 10 12 13 14 16 18 19 20 22 24 4 8 11 13 14 16 18 20 22 24 26 28 30 5 14 16 18 21 23 26 28 30 33 35 38 6 19 22 24 27 30 33 36 38 41 44 7 24 28 31 34 38 41 44 47 50 8 32 35 39 42 46 50 53 57 (P„DC3) = (P„DC4) = (P„DC6) = (P„DC7) = 3n + 2; if n €{1,2,4} 3 n + 3; otherwise ; if n = 2 lR (PnDC8) = { [f \ + 2; if n E {3, 4, 8} [^J + 3; otherwise 5.3 7R(CnOPk) for k G {2, 3,4, 5} and n > 3 We implemented this CctSG ctS ct rotagraph. From (3) we know that calculations in this case take much more time than calculations for fasciagraphs. Therefore we covered only cases for k E {2,3,4,5}. As in former cases, formulas for Roman domination number are presented below and constructions can be found on Figures 13 to 17. U Oh CD U CM «N lO CM u CD a CD > o s «n LO vD 0 Ö «n Qï o CM 1 CM 00 CM CM S CO CO CO CD ■ l-H CD CO J-H a CD U (C„aP2) 7fi(C„nP3) lR (Cnnp4) 1r {C„ap5) ??.; if /?. G {4A: | A: G N} n + 1; otherwise 7?. = 3 if n G {4A:,4A: + 1 | A: G N} otherwise 5; pfl; m +1; 7; if n = 3 2 /7 ; otherwise [^l+l; if nG {5fc + 2 | fceN} ; otherwise 5.4 7i?.(C„nCA-) for k e {3,4,5} In [12], authors showed that 7# (C^dCs™) = lOm/?., which is consistent with our calculations. We found no other formulas in the literature for these cases. Constructions for each case can be found on Figures 18 to 20. lR(CnaCs) 3 n lR (C„nC4) = 2n lR(CnaC5) 2n- if n G {5A: | A: G N} 2 n + 2; otherwise 6 Roman graphs Combining results obtained here and known results on the domination number [1, 5, 13, 19, 25] we also looked for Roman graphs (graphs, satisfying 7_r(G) = 27(G)). In cases where domination numbers of graphs have not been calculated, we also refer to a simple observation that a graph cannot be Roman if its Roman domination number is odd and to Proposition 16 in [6] which implies that a graph G is Roman if and only if it has a 7^-function / = (Vo,Vi,V2) with V\ = 0. Except in cases PnOC5, PnOC8, CnOP5 and C„DG5, the following are characterizations of Roman graphs among investigated. 1. Roman graphs among PnDPk: k = 1: ne {3/+ 2, 3/+ 3 | / G N0} o CM «n LO CM u CD a CD > o ¡5 «n LO vD 0 Ö «n o CM 1 CM 00 CM CM ¡5 CO CO k = 2 /?. odd k = 3 n G {4/ + 1,4/ + 2,4/ + 3 | / G N} k = 4 n G N\ {1,2,3,5,6,9} fc = 5 /?. G {1,2, 3, 7, 5/, 5/ + 1 | / G N} fc = 6 n G {1,3,5,7,8,12,15,22} fc = 7 n G {2,3,4,5,6,7,8,10,11,13,16} fc = 8 n G {1,4,6,7,8} fc = 4 k = 5 k = 6 k = 7 k = 8 2. Roman graphs among PnOCk- k = 3: n G {4/+ 1,4/+ 2 | / G N0} n > 2 nG {1,2,3} n E {1,3,4,6,6/ + 1,6/ + 3,6/ + 4,6/ + 6 | / G N} n G {2,4,2/ + 1 | / G N0} n G {1,2,3,4,5,6} 3. Roman graphs among CnOPk: k = 2: n G {4/, 4/+ 1, 4/+ 3 | / G N} n > 4 n G N\ {3,5,9} n G {3,4, 7, 8,10/, 10/ + 4,10/ + 7,10/ + 8 | / G N} 4. Roman graphs among C„nCfc: k = 3: n G {4/, 4/ + 1 | / G N} n G N n G {3,4, 5/, 5/ + 1, 5/ + 2, 5/ + 4 | / G N} k = 3 fc = 4 k = 5 k = 4 k = 5 Remark 6.1 It was proven in [25] that w + f <7 (P^Cn) < n + | ^ |. In fact, we show here that since Cwk^Ps, Cwk+^P^, Ciok+7^P5 and Ciok+s^Ps are Roman graphs (see Figure 17), their dominatin number equals CO CD ■ i-H u CD CO u a CD U References 10 CM $H CD a CD > o £ lO vD O Ö o CM CM 00 CM CM £ m m CO CD $H CD CO [1] S. Alanko, S. Crevals, A. Isopoussu, P. Ostergard and V. Pettersson, Computing the domination number of grid graphs, The Electronic Journal of Combinatorics, 18 (2011). [2] J. Arquilla and H. Fredricksen, "Graphing" an optimal grand strategy, Military Operations Research, Fall 1995. [3] B. Carre, Graphs and networks, Clarendon Press, Oxford, 1979. [4] E. W. Chambers, B. Kinnersley and N. Price, Extremal problems for Roman domination, SIAM Journal on Discrete Mathematics, 23(3) (2009), 1575-1586. [5] T. Y. Chang and E. O. Hare, Domination numbers of complete grid graphs, I, Ars Combinatoria, 38 (1994), 97-11. [6] E. J. Cockayne, P. A. Dreyer, S. M. Hedetniemi and S. T. Hedetniemi, Roman domination in graphs, Discrete Mathematics, 278 (2004), 11-22. [7] E. J. Cockayne, E. O. Hare, S. T. Hedetniemi and T. Wymer, Bounds for the domination number of grid graphs, Congressus Numerantium, 47 (1985), 217-228. [8] P. A. Dreyer, Applications and variations of domination in graphs, PhD thesis, Rutgers University, New Jersey, 2000. [9] M. H. El-Zahar, S. M. Khamis and Kh. M. Nazzal, On the domination number of the Cartesian product of the cycle of length n and any graph, Discrete Applied Mathematics, 155 (2007), 515-522. [10] O. Favaron, H. Karami, R. Khoeilar and S.M. Sheikholeslami, Note on the Roman domination number of a graph, Discrete Mathematics 309 (2009), 3447-3451. 11] D. C. Fisher, The domination number of complete grid graphs, manuscript, 1993. 12] X. Fu, Y. Yang and B. Jiang, Roman domination in regular graphs, Discrete Mathematics, 309 (2009), 1528-1537. 13] D. Goncalves, A. Pinlou, M. Rao and S. Thomasse, The domination number of grids, SIAM Journal on Discrete Mathematics, 25 (3) (2011), 1443-1453. 14] S. Gravier and M. Mollard, Note on domination numbers of Cartesian product of paths, Discrete Applied Mathematics, 80 (1997), 247-250. 15] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of domination in graphs, Marcel Dekker, New York, 1998. 16] T. W. Haynes, S. T. Hedetniemi and P. J. Slater (eds), Domination in graphs: Advanced topics, Marcel Dekker, New York, 1998. 17] M. A. Henning, A characterization of Roman trees, Discussiones Mathematicae. Graph Theory, 22 (2002), 225-234. 18] M. Juvan, B. Mohar and J. Zerovnik, Distance-related invariants on polygraphs, Discrete Applied Mathematics, 80 (1997), 57-71. U a CD U m CM Jh CD a CD > o £ lO VD O Ö ^ & O CM CM 00 CM CM £ CO CO [20 [21 [22 [23 [24 [25 [26 [27 [28 [29 [30 [31 [32 [33 S. Klavžar and N. Seifter, Dominating Cartesian products of cycles, Discrete Applied Mathematics, 59 (1995), 129-136. S. Klavžar and J. Zerovnik, Algebraic approach to fasciagraphs and rotagraphs, Discrete Applied Mathematics, 68 (1996), 93-100. M. Liedloff, T. Kloks, J. Liu and S.-L. Peng, Roman domination over some graph classes, Lecture Notes in Computer Science, 3787 (2005), 103-114. M. Liedloff, T. Kloks, J. Liu and S.-L. Peng, Efficient algorithms on Roman domination on some classes of graphs, Discrete Applied Mathematics, 156 (2008), 3400-3415. M. Livingston and Q. Stout, Constant time computation of minimum dominating sets, Congressus Numerantium, 105 (1994), 116-128. B.P. Mobaraky and S.M. Sheikholeslami, Bounds on Roman domination numbers of graphs, Matematiki vesnik, 60 (2008), 247-253. M. Nandi, S. Parui and A. Adhikari, The domination numbers of cylindrical grid graphs, Applied Mathematics and Computation, 217 (2011), 4879-4889. C.S. ReVelle and K.E. Rosing, Defendens Imperium Romanum: a classical problem in military strategy, The American Mathematical Monthly, 107 (7) (2000), 585-594. W. Shang and X. Hu, The Roman Domination Problem in Unit disk Graphs, Lecture Notes in Computer Science, 4489 (2007), 305-312. X. Song and W. Shang, Roman domination in a tree, Ars Combinatoria, 98 (2011), 73-82. I. Stewart, Defend the Roman Empire!, Scientific American, 281 (6) (1999), 136-138. X. Zhang, J. Liu, X. Chen and J. Meng, Domination number of Cartesian products of directed cycles, Information Processing Letters, 111 (2010), 36-39. J. !Zerovnik, Deriving formulas for domination numbers of fasciagraphs and rotagraphs, Lecture Notes in Computer Science, 1684 (1999), 559-568. J. Zerovnik, New formulas for the pentomino exclusion problem, Australasian journal of combinatorics, 36 (2006), 197-212. Y. Wu, An Improvement on Vizing's conjecture, manuscript, 2009. CO CD $H CD CO u a CD u 10 CM $H CD a CD > o £ lO vD O Ö o CM CM 00 CM CM £ m m —' ■>— —Ö )— — ft— — ft— n = 1 n = 2 n = 3 n = 4 n = 5 n = 6 n = 5k + 2 Yr = 12k + 6 1 1 t 11 1 t n = 5k + 3 i t n = 5k + 4 Yr = 12k + 11 n = 5k Yr = 12k + 2 1 1 , T i > 1 I , i I CO CD Jh CD CO n = 5k + 1 Yr = 12k + 4 Figure 3: PnaP,5 U a CD U 10 CM $H CD a CD > o £ lO vD O Ö o CM CM 00 CM CM £ m m n= 1n=2 n=3 n=4 n = 5 n = 5k + 2 Yr = 14k + 8 n = 5k + 3 YR = 14k + 10 n = 5k + 4 Yr = 14k + 13 n = 5k Yr = 14k + 2 «9- -i - i)- n = 6 1 1 1 1 1 1 1 1 1 1 1 1 i ^ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 CO CD Jh CD CO n = 5k + 1 Yr = 14k + 5 Figure 4: PnnP6 1 1 1 1 1 1 1 1 1 1 1 1 1 1 J U a CD U 10 CM $H CD a CD > o £ lO vD O Ö o CM CM 00 CM CM £ m m s— S- «9- - >- n= 1 n = 2 n = 3 n = 4 n = 5 n = 6 n = 7 n = 5k + 3 Yr = 16k + 12 n = 5k + 4 Y R = 16k + 15 n = 5k Yr = 16k + 2 n = 5k + 1 YR = 16k + 6 CO CD $H CD CO n = 5k + 2 Yr = 16k + 9 Figure 5: Pn^P7 U a CD U 10 CM $H CD a CD > o £ lO vD O Ö o CM CM 00 CM CM £ m m n = 1 n = 2 n = 3 n = 4 n = 5 n = 5k + 3 YR = 18k + 14 n = 5k + 4 Yr = 18k + 17 n = 5k Yr = 18k + 3 n = 5k + 1 Yr = 18k + 6 1 -i -< n = 6 n = 7 CO CD Jh CD CO n = 5k + 2 Yr = 18k + 10 Figure 6: PnaP8 U ft CD U 10 CM $H CD a CD > o £ lO vD O Ö o CM CM 00 CM CM £ m m n = 1 n = 2 n = 4k + 1 Yr = 6k + 2 n = 4k + 2 Yr = 6k + 4 n = 4k + 3 Yr = 6k + 5 n = 4k Yr = 6k + 1 n = 3 H«- n=4 ( i 8 I D \ I Mi Mi -to9- H«- i ( . i r i 1 i 1 I Ü I i ! M^- Figure 7: PnaCs Mi M^- Mi- CO CD $H CD CO It n = 1 n = 2 / I ill 1 AI ■i n = 3 n = 4 Figure 8: PnnC4 1 / ¡¡1 / il iv V n=5 U a CD U CM 10 CM $H CD a CD > o £ lO vD O Ö o CM CM 00 CM CM £ m m CO CD $H CD CO I It m «9 n=1 n=2 n=3 n = 4 n = 5 n = 6 n 5k + 2 nj n = 5k + 3 /TT7 n = 5k + 4 n = 5k tee- n = 5k + 1 ro 7R1 S9- Figure 9: Pn^C5 U a CD U 1 A 10 CM $H CD a CD > o £ lO vD O Ö o CM CM 00 CM CM £ m m CO CD $H CD CO i n LI L »- i <»— 1 I I- — v u \ n = 1 n = 2 n = 3 n = 4 jfrt- n=5 n=6 n = 6k + 1 Yr = 16k + 4 n = 6k + 2 Yr = 16k + 7 n = 6k + 3 Yr = 16k + 10 n = 6k + 4 YR = 16k + 12 n = 6k + 5 YR = 16k + 15 n = 6k + 6 Yr = 16k + 2 Tl / L r lr I 1 I - I » 1 l" I I - \ / L r r I I I i» /- 1 1 1. 1 - f- 1 - r I l. T \ ft i »—« L L L ! I I. Figure 10: PnnC6 Jh a CD U 10 CM $H CD a CD > o £ lO vD O Ö o CM CM 00 CM CM £ m m / 1 *— 11 - 1 » r — f n = 1 n = 2 n = 3 n = 4 n n=5 n=6 n = 7 T «— - 'l - i>— / /■ i, 1 a I / f / a \ i I 1 i \ n = 8 n=9 n =10 n =11 I / I / 1 l 1 \ I \ L — — • - > — s— - n n =12 n =13 n =14 1 - *— »- I - «- - ¡— 1 n =15 n = 14k + 2, yr = 42k + 9 Figure 11: PnaC7 m CD $H CD m u a CD U 10 CM $H CD a CD > o £ lO vD O Ö o CM CM 00 CM CM £ m m CO CD $H CD CO in n = 1 n = 2 n = 3 n = 4 n = 5 n=6 n = 7 n=8 n = 9 n =13 1 n =16 n =18 n = 20 - — /1 >— 1— It , \ i r 1 il •— *— t >— 1 n =10 n =11 n =12 J - — j — "~1 <— 11 ft— n =14 n =15 n =17 j — — ! It It - — ) — >— >— >— It It n =19 / - 1 1 n = 16k + 5, yr = 56k + 20 Figure 12: PnnC8 - — j — 1— 1— t 1— It 1 U ft CD U 10 CM $H CD a CD > o £ lO vD n = 4k Yr = 4k n = 4k + 1 Yr = 4k + 2 n = 4k + 2 Yr = 4k + 3 n = 4k + 3 Yr = 4k + 4 —®— — &— —®— —ii « —m— p-® i— —®— —®— 1« ¡>— Hi —®— —®— r-(SI i— -i i— Figure 13: CnnP2 o Ö o CM CM 00 CM CM £ CO CO n = 3 n = 4 n = 4k + 1 Yr = 6k + 2 n = 4k + 2 Yr = 6k + 4 n = 4k + 3 YR = 6k + 6 CO CD Jh CD CO n = 4k + 4 YR = 6k + 6 (S —m— —m—* 1 — i— -L —« Figure 14: C„nPa Jh a CD U 10 cm $H CD a CD > o £ lO VD O Ö o CM cm 00 cm cm £ m m CO CD $H CD CO n = 4k Yr = 8k n = 4k + 2 Yr = 8k + 4 n = 4k + 3 Yr = 8k + 6 n = 4k + 1 | Yr = 8k + 2 -ss- -fT —« p— 1 — 1 1 -^ p- H« 1 — ^ 1 ¡>— —s 5-f- 1 1 -r —g —- U^! 0— 1 -i- —Ü 9— - o £ lO vD O Ö o CM CM 00 CM CM £ m m CO CD $H CD CO «fcr- — 9— —« a— 1=** v___ -8 9- -<3 9-^ L4 —®— 9- (ii)— —<3 9- —<3 9- —(3 9^ n=3 n=4 n = 5 n = 6 n = 5k + 2 Yr = 12k + 6 n = 5k + 3 Yr = 12k + 8 n = 5k + 4 YR = 12k + 10 n = 5k + 5 Yr = 12k + 12 n = 5k + 1 Yr = 12k + 3 —e 9- —<3 9- - -- s>— —— -<3 S>- - p- - p- —- 9- Ig 9- -K >- -Ü 1- - 94 —<3 9- — -9 si— -U B- J 9- -4 9- — 9- — —<3 $— —<3 »— - -^ —<3 9- —<3 9- — - $- -13 B- -13 <3 9^- __^ -<3 9- 9- 9- 9- -0 9- <3 — 9- —<3 —« 3>- —1 3>- i —g 9- —i3 9-1 —<3 9- -(3 9- -<3 9- —<3 9- —<3 9- —<3 9-J Figure 16: C„DP5 U a CD U 10 CM $H CD a CD > o £ lO vD O Ö o CM CM 00 CM CM £ m m n = 10k YR = 24k n = 10k + 4 n = 10k + 7 Yr = 24k + 8 •— - - -""" —» - —( - 8- - 8- YR = 24k + 18 n = 10k + 8 Yr = 24k + 20 H - -f - Hi »— - S- - 1- Figure 17: CWI^P, Ciofc+4nP5, CW+zl^P and CW+sIlP are Roman graphs. CO CD $H CD CO u a CD u 10 CM $H CD a CD > o £ lO vD O Ö o CM CM 00 CM CM £ m m -U-A n = 3 n = 4k Yr = 6k n = 4k + 1 Yr = 6k + 2 n = 4k + 2 Yr = 6k + 3 n = 4k + 3 Yr = 6k + 5 n=6 ILA Figure 18: Cn^C3 ih[ -f —r a o—L —r —r J A A w \ ¡>-4- -i A :—r —r A A I 0 CO CD ■iH $H CD CO n = 3 n = 4 n = 5 Figure 19: Cn^C4 n=6 Jh a CD $H 10 CM $H CD a CD > o £ lO vD O Ö o CM CM 00 CM CM £ m m CO CD $H CD CO n = 3 n = 4 n = 5k YR = 10k n = 5k + 1 Yr = 10k + 4 n = 5k + 2 Yr = 10k + 6 n = 5k + 3 Yr = 10k + 8 n = 5k + 4 YR = 10k + 10 t > / ^_ ft —p t —\ \ w_____^ it t 3 * 9— ¡h^ — —f V " 1 v---- ^ ____^ St 7 9— -H - ¡1-4 g— V 1 Figure 20: CnnC5 IN U a CD U