IMFM Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia Preprint series Vol. 49 (2011), 1167 ISSN 2232-2094 A NOTE ON THE DOMINATION NUMBER OF THE CARTESIAN PRODUCTS OF PATHS AND CYCLES Polona Pavlic Janez Zerovnik Ljubljana, December 22, 2011 A note on the domination number of the Cartesian products of paths and cycles - d Polona Pavlic a Janez Zerovnik a'D a CD O CD Q IN vD £ CO CO CO CD ■ i-H U a Institute of Mathematics, Physics and Mechanics, Jadranska 19, Ljubljana 1000, Slovenia. b FME, University of Ljubljana, Aškerčeva 6, Ljubljana 1000, Slovenia. Abstract Using algebraic approach we implement a constant time algorithm for computing the domination numbers of the Cartesian products of paths and cycles. Closed formulas are given for domination numbers y(PnDCk) (for k < 11, n € N) and domination numbers 7(CnDPk) and 7(CnDCk) (for k < 6, n € N). o Key words: grid graph, torus, graph domination, path algebra, constant time algorithm 00 - 2010 Mathematical Subject Classification: 05C25, 05C69, 05C85, 68R10 1 Introduction Domination and its variations have been intensively studied and its algorithmic aspects have been widely investigated [9,10]. It is well known that the problem of determining domination number of arbitrary graphs is NP-complete [9]. It is therefore interesting to consider algorithms for some classes of graphs, including Cartesian products of paths and cycles. Exact domination numbers of the Cartesian products of paths PnOPk with fixed k were established in [1,2,3,5,8,17]. Formulas were given for k up to 19 [5,17] and in [1] Email addresses: polona.pavlic@imfm.si (Polona Pavlic), janez.zerovnik@imfm.uni-lj.si (Janez Žerovnik). Preprint submitted to Elsevier 22 December 2011 CM CM u CD CD Q r for k,n < 29. Recently Chang's conjecture stating that for every 16 < k < n, j(PnDPk) = I ("+2Hfc+'2) I _ 4 was proved hi [7], Domination number of the Cartesian product of cycles CnOCk, also known as tori, was studied in [4,12], In [12], exact formulas for all k < 4 and all n G N were given. Formula for k = 5 appears in [13], refering to an unpublished manuscript by the second author. Domination number of the Cartesian product of more than two cycles are investigated and in a special CctSG, ct formula was given [12]. Cartesian products of cycles and paths are considered in [15]: Exact values for CnOPk (A: < 4, n G N) are calculated and the domination number of CnOP5 is bounded. Exact values of j(CnOP5) for some n were given in [16], as they can be deduced from the Roman domination numbers. A general 0(log ??.) algorithm based on path algebra approach which can be used to compute various graph invariants on fasciagraphs and rotagraphs has been proposed in [13]. The algorithm of [13] can in most cases, including the computation of distance based invariants [11], the domination numbers [18] and Roman domination numbers [16] be turned into a constant time algorithm, i.e. the algorithm can find closed formulas for arbitrary n. The existence of an algorithm that provides closed formulas for domination numbers on grid graphs has been observed or claimed also in [5,14], Here we use the algorithm of [18] to find closed formulas for domination numbers of PnUCk and provide closed formulas (for k < 11 and n G N). Furthermore, closed formulas for the domination numbers of CnOPk and CnOCk (for k < 6 and n G N) are given. The new formulas are an improvement of known results and provide answer to some open questions from [12,15]. CM In the rest of this paper we first summarize the background for the main algorithm from in [18] and [19]. The algorithm is precisely presented in Section 3. In Section 4 we summarize results obtained by implementing the algorithm. Also some constructions for minimum dominating sets of investigated graphs are given. 2 Preliminaries • i-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 CM called a minimum dominating set, or shortly a 7-set. The Cartesian product of graphs G and H, denoted GdH, is a graph with vertex set V(G) x V(H) and two vertices (g, h) and (g', h') are adjacent if g = g' and hh' G E(H) or gg' G E(G) and h = h'. Examples of the Cartesian product graphs include the grid graphs, which are products of paths PnnPk, and tori, which are products of cycles CnnCk. Let Gi,..., Gn be arbitrary mutually disjoint graphs and X^ ..., Xn a sequence of sets of edges such that an edge of Xj joins a vertex of V(Gj) with a vertex of V(Gi+1). For convenience we also set Go = Gn, Gn+1 = G1 and X0 = Xn. A polygraph Qn = Qn(G1,... Gn; X1,... Xn) over monographs G1,... , Gn is defined in the following way: 00 CM CM ¡5 CO CO CD ■ 1 J-H CD W 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 Dj = {u G V(Gj) | 3v G Gj+1 : uv G Xj}, Rj = {u G V(Gj+1) | 3v G Gj : uv G Xj}. In general, RjHDj+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 un(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 PndPk are examples of fasciagraphs and that Cartesian products of cycles CnnCk are examples of rotagraphs. Products of a path and a cycle can be treated either as fasciagraphs or as rotagraphs. 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; (2) (P, o) is a monoid with e ◦ as a unit; (3) o is left- and right-distributive over ©; (4) Vx G P, x o e® = e® = e® o x. 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 P1 = a 3 (No U {oo}, min, +, oo, 0). Here No denotes the set of nonnegative integers and N the set of positive integers. 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,B G Ain(V) and define operations © and o in the usual way: CM J-H (.A © B)ij = Aij © Bij, n (A O 11): I = 0 Alk O Bkr k=1 o Mn(V) equipped with above operations is a path algebra with the zero and the unit matrix as units of semiring. In our example V\ = (N0U{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) = {t'i, t'2, • • • ,vn}. The labeling £ of G can be extended to paths in the following way: For a path Q = (t;io, v^)... (%_!, %) of G let £(Q) = t (vio, vh) o t (vi^vij o...o£ (yi^Vi^) . CM A(G)ij Let S^ be the set of all paths of order k from i\ to Vj in G and let A(G) be the matrix defined by: £ (iVj); if (vi, Vj) is an arc of G B; otherwise It is well-known that A(G)k)ti = 0 i{Q). 3 The domination number of fasciagraphs and rotagraphs CO • i-H Let us now summarize known results for determining the domination number of fasciagraphs and rotagraphs. The algorithm which computes different graph invariants on fasciagraphs and rotagraphs in 0(log ??.) time was proposed in [13] and then improved to run in 0(C) time for domination number [18] and also for some other graph invariants in [11,16,18,19]: Let wn(G; X) be a rotagraph and ^n(G; X) a fasciagraph. Set U = D U R = D U R and let N = 2|UDefine a labeled digraph G = G(G; X) as follows: The vertex set of G is formed by the subsets of U, denoted Vi. An arc joins a CM subset V with a subset Vj if V is not in a "conflict" with Vj• Here a conflict CM CM CD CD Q IN vO O o of V with Vj means that using Vi and Vj as a part of a solution in consecutive copies of G would violate the problem assumption. In the special case we are considering here, i.e. when computing the domination number, we introduce an arc between vertices V and Vj if Vi fl R fl D fl Vj = 0. Now consider for a moment ^(G; X) and let Vi C Di U Ri and Vj C D2 U R2 (of course R1 = R2 = R and D1 = D2 = D). Let ji,j (G; X) stand for the size of minimum dominating set of G2 \ ((Vi f R1) U (D2 f Vj)). Then we define a labeling of G, I : E(G) —> No U {to}, in the following way: l(Vi, Vj) = |Vi f R| + Yij(G; X) + |D f Vj | — |Vi f R f D f Vj |. (1) The following algorithm, first proposed in [13], computes the domination number of a fasciagraph or a rotagraph in O(log n) time: Algorithm 1 [13] (1) Let P1 = (N0 U {to}, min, +, to, 0) be a path algebra. (2) Label G(G; X) with the labeling, defined in (1). (3) In M(P) calculate A (G)n. (4) Let y (^ra(G; X)) = (A (G)n)oo and 7 (G; X)) = mint (A (G)n)t 1 CO n This algorithm can be improved: 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 domination numbers: Lemma 3.1 [18] Lei k = |V(G(G; X))| and K = |V(G)|. Then there is an index q < (2K + 2)k 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 Ar+sP = Ar + sC. Hence, if we assume that the size of G is a given constant (and n is a variable), 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. Therefore some additional improvements are welcome. One can also omit straightforward implementation of the algorithm. Instead of calculating whole matrices A(G)n, calculating only those rows which are important for the result and checking the a ¡5 CO CO GO CD ■ i-H a CD U difference of the new row against the previously stored rows until a constant difference is detected yields a correct result because of the following lemma. Lemma 3.2 [16] Assume that the j -th row of An+P and An differ for a constant, ajn+P^ = ajn^ + C for all i. Then min ajn+P^ = min ajn) + C. Jh 4 Summary .Q B We implemented the algorithm as described above and got results presented in the sequel. Calculations of y(PnmCk) for a fixed k were implemented as fasciagraph and calculations of 7(CndPk) and 7(CndCk) for a fixed k were implemented as rotagraphs. It is important to emphasize that calculations for fasciagraphs are a lot less time consuming than those for rotagraphs because Y W>n (G; X)) = (A (G )n Ooo and Y (wn(G; X)) = mini (A (G)U)ii ■ In other words, only one element of the matrix A (G)n is sufficient for the result on fasciagraphs 1 and a minimum over all diagonal elements of the same matrix is needed for rotagraphs. £ Theorem 4.1 Domination numbers of the Cartesian products of paths and cycles, where the size of one factor is fixed, can be in computed constant time, i.e. independently of the size of the second factor. Closed expressions for y(PnUCk), y(CnDPfc), and y(CnnCk) are given in Table 1 and in Table 2 for some values of k. 1 We also present constructions of Y-sets in some cases (see Fig. 1 -4). The patterns are enclosed in dashed boxes. In case of the graph PnnCn the pattern is shifted hence the period is 11 ■ 8 = 88. We conclude with a couple of remarks. Since every vertex of the Cartesian product of two cycles can dominate at most five vertices, it follows that Y(CnnCk) > nk. Adapting similar idea as in case of PnmCi0 to graphs C5mnC51 we have y(CndCk) < nk by construction. Therefore Y(C5mnC51) = 5ml. This result could also be deduced from results on Roman domination presented in [6]. By obvious reasoning we can extend constructions from Fig. 1 and Fig. 2 to obtain upper bounds for graphs PnOCm, see Table 3. We conjecture that the bounds are exact values for m = 5k, 5k + 1, 5k + 2, 5k + 4. Clearly as Y(CnDCm) < y(PnQCm), these are also upper bounds for the Cartesian product of cycles. CO Table 1 Domination numbers of PnnCk for a. fixed k. CSI •n k l(PnOCk) CSI CSI 3 m+1; if = 0 (mod 4) u CD £ Rrl; otherwise 4 n CD O CD Q *n 5 3; 4; if n = 2 if n = 3 n + 2 ; otherwise 1167 6 m; m+1; if n = 1 (mod 3) otherwise no. 7 m+1; [fl+2; if n = 1 (mod 2) otherwise •n o CSI 1 8 4; 6; 8; if n = 2 if n = 3 if n = 4 CSI 00 m+1; if n = 5 (mod 10) CSI CSI ¡5 CO CO HH m+2; otherwise 9 5; 7; 10 if n = 2 if n = 3 if n = 4 •n HH 2 n + 2; otherwise 10 2 n + 2; 2n + 3; if n < 5 if 6 < n < 9 •n CO 2n + 4 otherwise CD • i }-H 11 m + 1; if 7? € {1,2,4,6} or n = 3 (mod 8) CD CO + 2; otherwise +-> OH CD J-H cu CM CM J-H CD & B CD O CD Table 2 Domination numbers of the Cartesian products of paths and cycles for a fixed k. vO 0 •n o CM 1 CM 00 CM CM ¡5 CO CO CO CD ■ i-H J-H CD CO fc 7 (C„DCfe) 2 [§]+l; if?? = 2 (mod 4) ; otherwise 3 m 4 ?? + l; if?? €{5,9} ??; otherwise ?? 4; if ?? = 3 ??,; if ?? = 0 (mod 5) 5 Ixl +1; if ?? = 3,5,9 (mod 10) ?? + 2; if ?? = 3 (mod 5) [^P1]; otherwise ?? + l; otherwise 6 9; if ?? = 6 P^l+l; ?? = 2,6,7,9,13 (mod 14) [^y1]; otherwise [^1 + 1; ?? = 2, 3, 8, 9,11,14,15,17 (mod 18) j otherwise CM CM $H CD rO a CD O CD Q IN vO 0 o CM 1 CM CO CM CM £ CO CO Table 3 Upper bounds for the domination numbers of the Cartesian products of paths and cycles for n > m. 7(PraDCm) m = 5k k(n + 2) m = 5k + 1 (8fc+3)(ra+2) 8 m = 5k + 2 (2fc+1)(n+2) 2 m= 5k + 3 (k + 1)(n + 2) m= 5k + 4 (k + 1)(n + 2) m CD $H CD m u a CD U CM CM $H CD rO a CD O CD Q IN vO r — — 1 >— — ..... — I \ '1 • 1 — • 1 • ! k..... M rn u rn a: 0 o CM 1 CM CO CM CM £ CO CO 1 / " \ i I \ t rn CO CD $H CD CO ULU m u a CD U Fig. 1. Periodical behaviour of 7-sets of PnnCk for 3 < k < 8. T T CM CM u CD CD O CD Q m I I in vD 0 ^ & O CM 1 CM CO CM CM £ CO CO CO CD u CD CO a CD U Fig. 2. Periodical behaviour of 7-sets of PnnCk for 9 < k < 11. CM CM $H CD rO a CD O CD Q IN vO O Fig. 3. Periodical behaviour of 7-sets of CnOFk for 5 < k < 6. o CM 1 CM CO CM CM £ CO CO m CD $H CD m 1 ■-,-1- •..... ! I~1 --¡H --/ 1»-1 1 t—t --H — II-f" —j —f —/ --iH -- II- -—y —t —1 --H ~7 II-f- / 1 Ih-I- --- 1 1 1» --- II-- — 11— r 1 1 --- II-- 1 1 --H II-- --- 11— --^ II-- \ 1 I, ^ ! 1 I * -1 „ ^ ....... •-71-71-71-1- IH- / ~l --J --/ -- —/ --i"1 --1 ||-j- t—f -- —1 -- --( -- --/ ||- —( — / / 1 1 1 --- II-- --- II-- 1 1 --1- --- II-- --- II-- --- 11— --- 11— --h 1 1 II—t- --- 1 1 lh-j- --- 11— 1 1 --H II-- 1 1 --1- -- II-- — 11— 1 ^ 1 1 I, ^ „ 1 » ^ li - Fig. 4. Periodical behaviour of 7-sets of CnnCk for 5 < k < 6. U a CD U References [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). CM [2] T. Y. Chang, E. W. Clark and E. O. Hare, Domination numbers of complete grid graphs, I, Ars Combinatoria, 38 (1994), 97-11. & [3] E. J. Cockayne, E. O. Hare, S. T. Hedetniemi and T. Wymer, Bounds for the domination number of grid graphs, Congressus Numerantium, 47 (1985), 217228. CD [4] 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. vO Ö [5] D. C. Fisher, The domination number of complete grid graphs, manuscript, 1993. [6] X. Fu, Y. Yang and B. Jiang, Roman domination in regular graphs, Discrete Mathematics, 309 (2009), 1528-1537. [7] D. Gongalves, A. Pinlou, M. Rao and S. Thomasse, The domination number of grids, SIAM Journal on Discrete Mathematics, 25 (3) (2011), 1443-1453. [8] S. Gravier and M. Mollard, Note on domination numbers of Cartesian product of paths, Discrete Applied Mathematics, 80 (1997), 247-250. i [9] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of domination in graphs, Marcel Dekker, New York, 1998. CM [10] T. W. Haynes, S. T. Hedetniemi and P. J. Slater (eds), Domination in graphs: Advanced topics, Marcel Dekker, New York, 1998. [11] M. Juvan, B. Mohar and J. Zerovnik, Distance-related invariants on polygraphs, Discrete Applied Mathematics, 80 (1997), 57-71. I-H [12] S. Klavzar and N. Seifter, Dominating Cartesian products of cycles, Discrete Applied Mathematics, 59 (1995), 129-136. [13] S. Klavzar and J. Zerovnik, Algebraic approach to fasciagraphs and rotagraphs, Discrete Applied Mathematics, 68 (1996), 93-100. [14] M. Livingston and Q. Stout, Constant time computation of minimum dominating sets, Congressus Numerantium, 105 (1994), 116-128. "in e [15] M. Nandi, S. Parui and A. Adhikari, The domination numbers of cylindrical grid graphs, Applied Mathematics and Computation, 217 (2011), 4879-4889. [16] P. Pavlic and J. Zerovnik, Roman domination number of the Cartesian products of paths and cycles, manuscript. CM CM $H CD rO a CD O CD Q IN vO 0 o CM 1 CM CO CM CM £ CO CO m CD $H CD m u a CD U [17] A. Spalding, Min-Plus algebra and graph domination, PhD thesis, University of Colorado, 1998. [18] J. Zerovnik, Deriving formulas for domination numbers of fasciagraphs and rotagraphs, Lecture Notes in Computer Science, 1684 (1999), 559-568. [19] J. Zerovnik, New formulas for the pentomino exclusion problem, Australasian journal of combinatorics, 36 (2006), 197-212.