IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 50 (2012), 1181
ISSN 2232-2094
FORMULAS FOR VARIOUS DOMINATION NUMBERS OF PRODUCTS OF PATHS AND CYCLES
Polona Pavlic Janez Zerovnik
Ljubljana, September 11, 2012
Formulas for various domination numbers of products of
paths and cycles
Polona Paylič1'*and Janez Žerovnik1'2
1	IMFM, Jadranska 19, 1000 Ljubljana, Slovenia
2	FME, Aškerčeva 6, 1000 Ljubljana, Slovenia
September 1, 2012
■-Э
r i—i
00
о
CO CD
Jh
CD CO
и
a
CD U
Abstract. The existence of a constant time algorithm for solving different domination problems on the subclass of polygraphs, rotagraphs and fasciagraphs, is shown by means of path algebras. As these graphs include products (the Cartesian, strong, direct, lexicographic) of paths and cycles, we implement the algorithm to get formulas in the case of the domination numbers, the Roman domination numbers and the independent domination numbers of products of paths and cycles where the size of one factor is fixed, i.e. independently of the size of the second factor. We also show that the values of the investigated graph invariants on the fasciagraphs and the rotagraphs with the same monograph can only differ for a constant value.
AMS subject classifications: 05C25, 05C69, 05C85, 68R10
Key words: graph product, graph domination, path algebra, constant time algorithm, grids
СЧ -
CO
1. Introduction
CSI
Over years, extensive work has been done concerning the domination number and its variations, also from the algorithmic point of view [20, 21]. It is well known that the problem of determining the domination number and different variations of the domination number of arbitrary graphs is NP-complete [21]. It is therefore worthwhile to consider algorithms for some classes of graphs, including all four standard products of paths and cycles. Known results on the domination, Roman domination, total domination and independent domination of the Cartesian product of paths and cycles are shown in Table 1 and known results on the strong and the direct product of paths and cycles can be found in Table 2. In cases where more general results are known, only those are listed. For the lexicographic product of graphs, exact formulas for the domination, the total domination and the independent domination numbers can be easily obtained and can be found, for instance, in [33]. Recently also the Roman domination number of the lexicographic product of graphs was investigated in [31]. The domination number of the Cartesian and the strong graph bundles were studied in [42]. Graph bundles represent a well known generalization of graph products [36].
* Corresponding author. Email addresses: polona.pavlic@imfm.si (Polona Pavlic), janez.zerovnik@fs.uni-lj.si (Janez Zerovnik)
О
сч
я
1—1
00
0 Ö
о
сч
1
сч со сч сч
г
со со
со
CD
CD СО
A general O (log n) algorithm based on path algebras, which can be used to compute various graph invariants on the fasciagraphs and rotagraphs, has been proposed in [26]. The algorithm of [26] can in most cases, including the computation of distance based invariants [25], the domination numbers [34, 40], the Roman domination numbers [35] and others [24, 41] be turned into a constant time algorithm, i.e. the improved algorithm can find closed formulas for arbitrary number of monographs in a fasciagraph or a rotagraph. The existence of an algorithm that provides closed formulas for the domination numbers on grid graphs has been observed or claimed also in [16, 32]. Other approaches for investigating graph invariants on polygraphs can be found in [7].
Here we generalize the algorithm of [40] to compute so-called ^-domination numbers of fasciagraphs and rotagraphs. This means that for (almost) any kind of domination type (whether we look for domination number, Roman domination number, total domination number, independent domination number, k-domination number, etc.), we are able to find exact formulas on fasciagraph and rotagraphs, for any number of monographs. As fasciagraphs and rotagraphs include different products of paths and cycles, the results of the implementation of this generalized algorithm, which can be found in Tables 3 - 10, complement previously known results of Tables 1 and 2.
In the rest of this paper we first recall the background for the main algorithm from [26] and [40]. In Section 3, the algorithm, which generalizes and improves the space complexity of the algorithm from [26, 40] is precisely presented. Summary of results is given in Section 4. In particular, the properties of the new algorithm allow us to improve best known results in several cases. A short conclusion then ends the paper.
Graph invariant
Table 1: Known results for the Cartesian product
The Cartesian product
Y (PnOPk ) =
(n+2)(k+2) 5
- 4 for n,k > 16, [17],
Domination
other results: [1, 10, 13, 16, 19, 38], Y(CnDPk), for k < 11 and n G N; [34], Y(PnüCk), y(CnDCk) for k < 6 and n G N, [34].
Roman domination	YR(PnOPk), YR(CnUPk), for k < 8 and n G N, [35], Yn(PnOCk), YR(CnDCk) for k < 6 and n G N, [35].
Total domination	Yt(PnüPk) for k < 4 and n G N [18], Yt(PnDPk) for k = 5, 6 and n G N [29], bounds for Yt(PnDPk) for k, n > 16 [18].
Independent domination	i(PnDPk) for k < 14 and n G N [14]
U
a
CD U
О
СЧ
1—1
00
0 Ö
о
СЧ
1
СЧ CO СЧ СЧ
г
CO CO
Table 2: Known results for the strong and the direct product
CO CD
CD CO
и
a
CD U
Graph invariant	The strong product	The direct product
Domination	Y(G H H) < Y(G)Y(H), Y(T H H) = Y(T)Y(H), where T is a tree, [33].	Y(Pn X Pk) for k < 6, [27, 28], for k < 9 [11], further results for k < 33 and n < 40 [11].
Roman domination	Yr(GH H) < 2Y(G)Y(H), [39].	-
Total domination	Yt(G H H) < Yt(G)Y(H), [33].	Yt(T X H)= Yt(T)Yt(H), where T is a tree, [37]. Yt(Cn X Ck) for n, k G N [15]
Independent domination	i(Pn H Pm), i(Cn H Cm), i(Pn H Cm), n, m G N, [30].	-
2. Preliminaries
We consider finite undirected graphs and directed graphs (digraphs). An edge between vertices u and v in an undirected graph will be denoted uv while in a digraph, an arc between vertices u and v will be denoted (u,v). Pn stands for a path on n vertices and Cn for a cycle on n vertices. For u G V (G), N (u) = {v G V (G) | uv G E (G)} is an open neighborhood of u and N [u] = N (u) U {u} a closed neighborhood.
Here we show that different variations of the graph domination problems can be solved in constant time on fasciagraphs and rotagraphs. Because there are so many graph invariants, related to the domination number, many authors tried to unite them or present them in a way. Some of the classifications can be found in [5, 6, 8, 20, 21]. We will refer to them as defined in the sequel:
Definition 1. Let G = (V(G),E(G)) be a graph, a, > 0 for i = 0,..., I and f * : V(G) —> {ao, ai,.. ., ai} a function. Let (Vo, Vi, V2,.. ., V) be ordered partition of V (G) induced by f *, where V = {v G V (G) | f *(v) = a,} for i = 0,1,...,1. Note that there exists a 1-1 correspondence between the functions f * : V(G) —> {ao, ai,. .., ai} and ordered partitions (Vo, Vi,. .., V) of V(G). Thus, we write f * = (Vo, Vi,. .., V). The weight of f * is defined as:
w(f *)= E f* (v).
vev(G)
A function f * = (Vo, Vi, .. ., Vi) is called a *-dominating function if a "particular statement *" holds for f *. The *-domination number equals
Y*(G) = inf{w(f *) | f * is a *-dominating function of G}.
(1)
We say that a function f is 7* -function if it is a *-dominating function of weight Y*(G).
O
CSI

m
CD
4—I
и
CD
U
a
CD U
This general definition unites many known domination types, let us mention some:
1. Let I =1, a, = i for i = 0,1 and let statement * be that:
(a)	every vertex of V0 has a neighbor in Vi. Then Definition 1 is a definition of the domination number, y(G).
(b)	every vertex of V(G) has a neighbor in Vi. Then Definition 1 is a definition of the total domination number, yt(G) [23].
(c)	every vertex of Vo has a neighbor in Vi and the set Vi is an independent set (i.e. no edge joins two vertices of Vi). Then Definition 1 is a definition of the independent domination number, i(G) [2].
00
2.	Let I = 2, a, = i for i = 0,1, 2 and let statement * be that every vertex of V0 has a neighbor in V2. Then Definition 1 is a definition of the Roman domination number, 7r(G) [12].
3.	Let I = k +1, a, = i for i = 0,1,..., I and let statement * be that every vertex of V0 is defended (i.e. has a neighbor in V, for some i > 1) and for any sequence v1,...,vk of (not necessarily distinct) vertices, there exists a sequence of functions f = f0, f1,..., fk such that for i = 1,..., k, (i) either fi-i(vi) > 0, in which case f, = f,-i, or fi-i(v-) = 0, in which case f, is obtained from fi-1 by one movement to v,, and (ii) f, has no undefended vertex. For more detailed definition see [22]. Then Definition 1 is definition of the k-Roman domination number, 7R (G).
СЧ
In the sequel we will focus our attention to finding *-domination numbers of four standard products of graphs. For graphs G and H, the vertex set of these products is always the same, V (G) x V (H ). Two vertices are adjacent in the:
1.	Cartesian product, GUH, if and only if g = g' and hh' G E(H) or gg' G E(G) and h = h';
CO
2.	strong (normal) product, G H H, if and only if g = g' and hh' G E (H ) or gg' G E(G) and h = h' or gg' G E(G) and hh' G E (H );
3.	direct (also known as tensor, cardinal, categorical, Kronecker) product, G x H, if and only if gg' G E(G) and hh' G E(H);
4.	lexicographic product, G [H], if and only if gg' G E (G) or g = g' and hh' G E (H ).
Let G1,..., Gn be arbitrary mutually disjoint graphs and X1,..., Xn a sequence of sets of edges such that an edge of X, joins a vertex of V(G,) with a vertex of V (G,+ i ) (X, С V (G,) x V (G,+ i) for i = 1,..., n). For convenience we set Gn+1 = G1. A polygraph Qn = Qn(G1,... Gn; X1,... Xn) over monographs G1,..., Gn has the vertex set V(Qn) = V(G1) U ... U V(Gn), and the edge set E(Qn) = E(G1) U X1 U ... U E(Gn) U Xn. For a polygraph Qn and for i = 1,..., n we also define
D, = {u G V (G,) | 3v G G,+i : uv G X,},
Ri = {u e V(Gi+1) | 3v e Ci : uv e XJ.
сч	In general, Ri П Di+1 does not have to be empty. If all graphs Gi are isomorphic
to a fixed graph C (i.e. there exists an isomorphism : V(Ci) —> V(C) for i = 1,... , n + 1, and y>n+1 = y>i) and all sets Xi are equal to a fixed set X С V (C) X V (C) ( (u, v) e X ^^ (^r1(u), ^^(v)) e Xi for all i), we call such a graph rotagraph, wn(C; X). A rotagraph without edges between the first and the last copy of C is fasciagraph, ^n(C; X). More precisely, in fasciagraph, Xn = 0 and X1 = X,..., Xn_1 = X. In rotagraph as well as in fasciagraph, all sets Di and Ri are equal to fixed sets D and R, respectively (Di = -1(D) and Ri = ^_+11(R)). Of course, in a case of fasciagraphs, Dn = 0 and Rn = 0. Let for a moment C • H denote any of the graph products, □, H, X or the lexicographic. Observe that products of paths Pn • Pk are examples of fasciagraphs and that products of cycles Cn • Ck are examples of rotagraphs. Products of paths and cycles can, except in the case of non-commutative products (the lexicographic product), be treated either as fasciagraphs or as rotagraphs. Polygraphs, which were first studied in [3], also include a generalization of a graph product, that is graph bundles, introduced in [36].
A semiring P = (P, ф, о, e®, e0) is a set P on which two binary operations, ф and о are defined such that (P, ф) is a commutative monoid with e® as a unit, (P, о) is a monoid with e0 as a unit, о is left- and right-distributive over ф and for every x e P, x о e® = e® = e® о 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 e0 ф e0 = e0 holds for e0 , the unit of the monoid (P, о). An important example of a path algebra for our work is P1 = (No U {то}, min, +, то, 0). Here N0 denotes the set of nonnegative integers and N the set of positive integers.
Let P = (P, ф, о, e®, e0) be a path algebra and let Mn(P) be the set of all n X n matrices over P. Let A, B e Mn(P) and define operations ф and о in the usual way: £ y
(A ф B)ij = Aij ф Bij,
CO
о
CSI
I
и
a
CD U
(A о B)ij = 0 Aik о Bkj.
k=1
Mn(P) equipped with above operations is a path algebra with the zero and the unit matrix as units of semiring. In our example P1 = (N0 U {то}, min, +, то, 0), all elements of the zero matrix are то, the unit of the monoid (P, min), and the unit matrix is a diagonal matrix with diagonal elements equal to e0 =0 and all other elements equal to e® = то. Sometimes, we will also need ordinary matrix summation CO	in R (i.e. (A + B)ij = Aij + Bij). We denote it with ordinary +.
Let P be a path algebra and let C be a labeled digraph, that is a digraph together with a labeling function I which assigns to every arc of C an element of P. CD	Let V(C) = {v1, v2,..., vn}. The labeling I of C can be extended to walks in the
following way: For a walk Q = (vi0, v^ Xv^, vi2 )... (vik-1, vik ) of C let
= ^ (vi0 , vil ) о ^ (vil , vi2 ) о ... о 1 (vifc-1 , vik )
О
сч
1—1
00
0 Ö
о
сч
1
сч со сч сч
г
со со
Let Sjj be the set of all walks of order k from vi to Vj in G and let A(G) be the matrix defined by:
(A(G))j
It is well-known [9] that
I (vj, Vj) ; if (vj, Vj) is an arc of G
сФ •
otherwise
(2)
(A(G)kL = 0 l(Q).

3. Algorithm for determining *—domination numbers of fasci-agraphs and rotagraphs
Let us now present a constant time algorithm for determining ^-domination numbers of fasciagraphs and rotagraphs. As mentioned before, the algorithm which computes different graph invariants on fasciagraphs and rotagraphs in O(log n) time was proposed in [26] and then improved to run in O(C) time for the domination number [40] and also for some other graph invariants in [25, 35, 41]. We now generalize this algorithm in the following way:
Let w„(G; X) be a rotagraph and ^„(G; X) a fasciagraph as defined above. Set U = D U R. (Keep in mind that Di С Gì and R C Gi+1, but since Ri = R and Di = D for i = 1,..., n in case of rotagraphs and for i = 1,..., n — 1 in case of fasciagraphs, we can write U = Di U Ri = D U R). A labeled digraph G = G (G; X) is a graph with a vertex set:
V (G ) = {vi = (Vj, Vj, ...,VÌ) I Vj C U and Vjj П Vhj = 0 for 0 < j, h < l, j = h} .
In particular, v0 = (V00, V0,..., V;0) stands for (0, 0,..., 0).
Let vi, vj G V (G) and consider for a moment ^(G; X ). Let V0j U V1i U ... U Vj C D1 U R1 and V0j U Vj U ... U Vj C D2 U R2. (Note that we use the notation D1 U R1 and D2 U R2 instead of D U R here only to be clear about the general idea.) Let Yjj(G; X) be the weight of a 7*- function of a graph G2 \
((R1 n (V0j U V/ U ... U Vj)) U ( (V0j U Vj U ... U Vj) n D2)), such that Vhj U Vj С Vh for h = 0,..., l where (V0, V1,... V ) is a ^-dominating function of a graph G2. For consistency, we introduce an arc between vertices vi and v j only if Vj n Vjj = 0 for all 0 < h1, h2 < l, h1 = h2. Set
CO CD
Jh
CD
m
и
a
CD U
*(vj, vj ) = E ah I Vj n R| + 7jj (G; X) + E
ан
h=0
h=0
Vj n D
— E
ah
h=0
Vhi n D n R n Vhj
h=0
h=0
(3)
Remark 1. If D n R = 0, then equation (3) is reduced to
t(vi, vj) = E ан |Vj n R| + Yjj (G; X) + E ан
Vhj n D
Now, considering graph G(G; X) and labeling (3), form a matrix A (G) as defined
СЧ
00
о
CO
и
a
CD U
in (2). Then, according to [26], we have an algorithm which computes ^-domination number of rotagraphs and fasciagraphs in O (log n) time:
Algorithm 1
1.	For a path algebra select P = (No U {то}, min, +, то, 0).
2.	Label G = G (G; X ) as defined above.
3. In M (P) calculate A (G)n.
4. Let 7* (V„(G; X)) = (A (G )n)oo and 7* K(G; X)) = min (A (G)n)w.
Theorem 1. The Algorithm 1 correctly computes * -domination number of rotagraphs and fasciagraphs:
О
Y* (WG; X)) = (A (G)n)oo	(4)
Y* K(G; X)) = min (A (G)n)„	(5)
in O (log n) time.
Proof. Let Gi and G2 be arbitrary graphs, Xi a set of edges between vertices of G1 and G2 and let Q2(G1,G2; X1,0) be a polygraph. Let also P = (No U {то}, min, +, то, 0) be a path algebra and let G' be a labeled digraph for Q2 defined similarly as above. Then, by the definition of labeling, we have
Y* («2 (Gi, G2; Xi, 0)) = [A(Gi) + A(G2)]oo
=	,№o,vfc ) + , vo)}.
VfcGV (G)
CO
Let G1 = G, X1 = X and G2 = ^n-1(G; X). Then (4) follows by induction.
For (5), similarly, consider Q2(GbG2; X1,X2) and let G1 = G, X1 = X2 = X and G2 = ^n-i(G;X).
It is well known that, in general, Step 3 of the algorithm can be implemented to run in O(log n) time and other steps can be done in a constant time. Therefore Algorithm 1 can run in O (log n) time.	□
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, so called "cyclicity lemma", which was proposed in [4] and used in a similar way in [34, 35, 40, 41].
Lemma 1. Let N = |V(G(G;X))|, K = |V(G)| and a = max{ao,...,a;}. Then there is an index q < (2aK + 2)N such that Aq = Ap + C for some index p < q and some constant matrix C = [c]j. Let P = q — p. Then for every r > p and every
s > 0 we have
Ar+sP = Ar + sC.
О
сч
Proof. First observe that for any k > 1, the difference between any pair of entries of Ak, both different from то, is bounded by 2aK: Assume (Ak)*j = то. Then

(A% = Y*
V (Gl) \ ( U Vh ) ) и V (G2) u ... U V (Gk-1 ) U ( V (G k) \ ( U Vj
h=0
Vh=0
< y*(^(G;X)).
Since УД n Vh = 0 and Vj П V j = 0 for h1,h2 =0,... ,l and because of the choice of a it follows that
00
0 Ö
о
сч
1
сч со сч сч
£ со со
со
CD
CD СО
а
CD U
J2ah Iv* п R| + ]Г
ah
h=0
h=0
Vj n D
< 2aK.
According to (3) we have
l(v*,vj) < 2aK + (G; X) - ^
ah
h=0
V* n D П R П Vj
Therefore
< 2aK + (G; X ) = 2aK + (Ak).. (Ak ).. > ^(vj, vj ) - 2aK > y* ^k (G; X )) - 2aK.
Y* (^(G; X)) - 2aK < (Ak)*j < 7*(^(G; X))
For k > 1, let Mk = min{(Ak )ij} and let (Ak)' = Ak - (Mk)J, where J is the matrix with all entries equal to 0 (recall that we are still in the path algebra P = (No U {то}, min, +, то, 0)). Since the difference between any two elements of Ak, different from то, cannot be greater than 2aK, the entries of (Ak)' can have only values 0,1,..., 2aK, то. Hence there are indices p < q < (2aK + 2)N such that (Ap)' = (Aq)'. This proves the first part of the lemma.
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) о E = D o E + C, where + is the ordinary matrix addition, i.e. (A + B)*j = A*j + B*j for all i, j:
((D + C) о E)jj = min{((D)*k + C) + (E)kj} = min{(D)*k + (E)kj} + C kk
(D о E + C)jj = min{(D)ik + (E)kj} + (C)*j = min{(D)*k + (E)kj} + C. kk
Therefore, let Aq = Ap + C for some index p < q and some constant matrix C = [c]*j. Then
Aq+1 = (Ap + C) о A = (Ap o A) + C = Ap+1 + C.
i-Ч
00
Let P = q — p and r > p. Then also
Ar+P = Ar+q-p = Aq o Ar-P
= (Ap + C) o Ar-p = Ap+r-p + C = Ar + C,
and by induction on s we have
Ar+sP = Ar+P+(s-i)P = (Ar + C) 0 A(s-1)P = Ar+(s-1)P + C = Ar + (s — 1)C + C = Ar + sC for every s > 0.	□
Remark 2. Assume that one looks for:
1.	a domination or total domination or independent domination number of a fasciagraph or a rotagraph. Then q < (2K + 2)N . For instance, if fasciagraph is a grid graph PnOPk, then q < (2k + 2) .In particular, if к = 4, q < 10 .
2.	a Roman domination number of a fasciagraph or a rotagraph. Then q < (4K + 2)N . For instance, if fasciagraph is a grid graph PnDPfc, then q < (4k + 2)23k . In particular, if к = 2, q < 1064.
We see that already in cases of very small monographs, enormously large q are obtained. That is why the second part of Lemma 1 is useful for practical purposes -once a period is detected, it cannot change. When we implemented the algorithm for CO	various domination problems and smaller monographs, the period was always found
much sooner - at latest for q = 20.
So, if we assume that the size of a monograph G is a given constant (and n is a variable), the algorithm will run in constant time. However, straightforward implementation may not be practical due to obvious large space requirements of the algorithm. Fortunately, instead of calculating whole matrices An, calculating only those rows which are important for the result and checking the 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, first presented in [41] and recently generalized in the following way:
Lemma 2. [35] Assume that the j-th row of An+P and An differ for a constant, an++P = ani + C for all i. Then minž an+P = minž aj^ + C.
This immediately gives an improvement in the case of fasciagraphs: recall that 7* (-0n(G; X)) = (A (G)n)oo. For computing 00-th element of An we only need first rows of matrices Ai for 2 i n 1:
Ani = min {An-1 + Ab} . к
U
a
CD U
In the case of rotagraphs such an improvement is not crucial because 7* (wn(G; X)) = mini (A (G)n)ii. Therefore we prove that once we have a period for a fasciagraph
фп(С; X), the same period is optimal for шп(0; X), in other words, formulas for fas-
СЧ
□
ciagraphs and rotagraphs with the same monograph G can only differ for a constant value. In particular, there can be at most P different constants for which fasciagraph and rotagraph differ:
Lemma 3. Let Aq = Ap + C and P = q — p. Then for every t e 0,1,..., P - 1 there is a constant Ct such that for all n > p with t = (n — p) (mod P) we have
7*(фп (G; X )) — Y >n(G; X )) = Ct.
Proof. Let Aq = Ap + C for some q > p and a constant matrix C = [c]j. Such p, q, C exist because of the Lemma 1. We can write n = p + sP +1, where P = q — p, s > 0 and 0 < t < P. Then An = Ap+sP+t = Ap+t + sC also by Lemma 1 and we
00
have:
yWG; X )) — Y >n(G; X )) =(An)00 — min {(An)iJ
i
= (AP+t + sC)oo — min {(Ap+t + sCU Й	= (AP+t)oo + sC — mm {(AP+t)ii} — sC
= (AP+t)oo — min {(Ap+t)ii} = Ct.
СЧ
4. Summary of results
Theorem 2. *-domination numbers of fasciagraphs and rotagraphs can be computed in constant time, i.e. independently of the size of a monograph G.
Proof. Algorithm 1 implies an O (log n) algorithm for computing ^-domination numbers of fasciagraphs and rotagraphs. When applying Lemma 1, we get closed expressions for ^-domination numbers of fasciagraphs and rotagraphs.	□
CO
In special cases we have:
I—I
Corollary 1. Domination numbers, Roman domination numbers and independent domination numbers of the Cartesian, strong, direct or lexicographic 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.
A summary of results of our implementation of the algorithm is given in the next proposition. Additional formulas, found by an earlier version of our algorithm, can be found in [35] for the Roman domination numbers of the Cartesian products of
CD
paths and cycles and in [34] for the domination numbers of the Cartesian products of paths and cycles.
CD
Proposition 1. Closed expressions for:
1. Y(Pn X Pk), Y(Pn x Ck), Y(Cn X Pk) and Y(Cn x Ck) for some fixed k are given in Tables 3 and 4;
• ^ a
CD
2. Yr(Pu x Pk), Yr(Pu x Ck), yr(C X Pk) and 7д(С„ x Ck) for some fixed k
СЧ
s
и
a
CD U
are given in Tables 5 and 6.
3. i(PnaPk), i(PnaCk), i(CnaPk), i(CnnCk) and i(Pn x Pk), i(Pn X Ck), i(Cn X Pk), i(Cn X Ck) for some fixed k are given in Tables 7 - 10.
In the tables, previously known results are shaded gray. Note that the independent domination number is not monotone and therefore it can happen that i(PnDPk) > i(PnDCk) in some cases.
5. Conclusion
i—l
1.	The aim of this paper was to generalize and improve the results of the domination number on polygraphs from [26, 35, 40]. We have shown that almost any variation of the domination number can be solved in constant time on polygraphs. The only restriction, which is applied in the proof of Lemma 1, is actually that the "labels" of the vertices must be nonnegative. If some are negative, then Algorithm 1 still yields an O(log n) algorithm on polygraphs.
2.	When one implements the improved algorithm, calculations for rotagraphs take much more time that the ones for fasciagraphs. Lemma 3 indicates a step forward in a sense that the results for rotagraphs can be deduced from the results for fasciagraphs. Particularly, the values for rotagraph and for fasciagraphs with the same monograph can only differ for a constant value.
I
3.	The improved algorithm allows us to improve many best known results for the domination number and others (see Tables 1, 2). The results of Tables 3-10 could, according to the theoretical results, be extended for larger monographs.
2	We implemented the improved algorithm on personal computer and later on
a small computer cluster. Therefore, due to time constraints, we did not compute any additional formulas. But with a little help of technology we could produce more results. Moreover, we restricted our attention to the domination, Roman domination and independent domination number. One could go even further and implement the algorithm for other domination types that satisfy the definition of ^-domination.
4.	Another avenue of research was initiated recently in [7] where the properties of invariants, allowing such an algorithm to be applied to polygraphs, were investigated. On the other hand, here restriction to certain type of domination problems led to improvements in speed. It may be interesting to investigate whether and under what additional conditions Lemma 1 and Lemma 3 can be valid for a larger class of graph invariants.
О
сч
я
1—1
00
0 Ö
о
сч
1
сч со сч сч
г
со со
Table 3: Domination numbers for the direct products Pn X Pk and Cn X Pk, к = 3,..., 11 and n > 3.
CO CD
Jh
CD CO
и
a
CD U
10
11
k		Y(Pn X Pk)		Y(Cn X Pk)
3	n		n	
	n;	if n = 0 (mod 4)	n;	if n = 0 (mod 4)
4	n + 1;	if n = 1 , 3 (mod 4)	n + 1;	if n = 1 , 3 (mod 4)
	n + 2;	otherwise	n + 2;	otherwise
	5;	if n = 3	
	6;	if n = 4	Г4f 1 + 1; if n = 2 (mod 6) |"4n] ; otherwise
5	11;	if n = 7	
	Г 1+1;		
		if n = 2 (mod 3)	
	Г 4P 1 +2;	otherwise	
	5; if n = 3	ГЩ? 1 + 1; if n = 4, 8 (mod 10) I"8?] ; otherwise
6	Г1 + 1; if n = 3,4 (mod 5) [t?] ; otherwise	
		
	14;	if n = 7	Г ¥ 1+1; Г 1 + 2; Г9т1 ;	
7	Г 9n 1 ; Г 1 +1; Г 1 +2;	if n = 4 (mod 5) if n = 1, 3 (mod 5)		if n = 1, 6, 8 (mod 10) if n = 2 (mod 10) otherwise
		otherwise		
2n; if n = 0 (mod 4) 2 n + 2 otherwise
2n; if n = 0 (mod 4) 2n + 2 otherwise
10: 17;
Г ¥ 1 +
2:
Г ¥ 1 + 3;
if n = 4 if n = 7
if n = 0,1, 3, 6, 7, 8
(mod 10) otherwise
16;	if n = 6
24;	if n = 9
26;	if n = 10
Г 1+2	if n = 3, 4, 8 (mod 10)
г 1+3	if n = 1, 2, 6, 7 (mod 10)
Г ^ 1 +4	otherwise
12;	if n = 4
Г ^ 1+3	if n = 3, 5, 9,13,19
Г ^ 1+2	if n = 6, 7,11,12
Г ^ 1+3	if n = 1, 4, 7, 8 (mod 10)
Г ^ 1 +4	otherwise
8
9
О
СЧ
1—1
00
0 Ö
о
СЧ
1
СЧ CO СЧ СЧ
г
CO CO
Table 4: Domination numbers for the direct products Pn X Ck and Cn X Ck, k = 3,..., 11 and n > 3.
CO CD
Jh
CD CO
k	Y(Pn X Cfc )			y(C„ X Cfc)
3	Г 1; Г 1+1	if n = 2 (mod 3) ; otherwise	Г	3; if n = 3 4; if n = 4 2p] ; otherwise
	n;	if n = 0 (mod 4)	n;	if n = 0 (mod 4)
4	n + 1;	if n = 1, 3 (mod 4)	n + 1;	if n = 1, 3 (mod 4)
	n + 2;	otherwise	n + 2;	otherwise
			n;	if n = 0 (mod 5)
5		n+2	n + 1 n+2	; if n = 1 (mod 5) ; otherwise
6	Г 1+1 Г 1 +2:	if n = 2 (mod 3) otherwise	8; Г Г1 + rf 1	if n = 4 1; if n = 2 (mod 6) ; otherwise
7	Г 1+3:	if n = 2 (mod 4)		
	Г 1 + 2	otherwise		
8	2n;	if n = 0 (mod 4)		2n
	2n + 2	otherwise		
	2n + 2;	if n = 0, 2, 4, 5, 8,11		
9	2n + 3	(mod 12) otherwise		
10		2n + 4		
	12;	if n = 4		
11	Г 7-f 1+3: Г f 1 +4:	if n = 2 (mod 3) otherwise		
и
a
CD U
О
сч
Table 5: Roman domination numbers for the direct products Pn X Pk and Cn X Pk, k = 3,..., 9 and
n > 2.
1—1
00
0 Ö
о
СЧ
1
СЧ CO СЧ СЧ
г
CO CO
CO CD
Jh
CD CO
k		Yr(P? x Pk)			Yr(C? X Pk)
3	г 3? 1		if n = 2 (mod 4)	Г 3? 1 +	1; if n = 2 (mod 4)
	Г 3?	1 1; 1;	otherwise	Г 3? 1	otherwise
		6;	if n = 2		
4		12; 2n;	if n = 5 otherwise		2n
	Г 8?	1;	if n = 0 (mod 3)	Г 8? 1 ;	if n = 0, 3, 5 (mod 6)
5	Г 8? 1	1;	if n = 1 (mod 3)	Г 8? 1+1;	if n = 1, 4 (mod 6)
	m + 2;		otherwise	Г 8? 1 +2;	otherwise
	12		if n = 2		
6	24 3n		if n = 6 if n = 0 (mod 2)		3n
	3n +1;		otherwise		
	10		if n = 2		
	11		if n = 3		
7			if n = 5		
	г 20 Г 1Jt Г 13?1 Г^ 1	1; + 1; + 2;	if n = 1 (mod 3) if n = 2 (mod 3) otherwise		
		12	if n = 2		
8		24 4n;	if n = 5 otherwise		4n
	12		if n = 2		
	14		if n = 3		
9	Г13? 1 Г 13?1 +	; 1;	if n = 4 (mod 6) if n = 1, 2 (mod 6)		
	Г1!?! +2;		otherwise		
и
a
CD U
О
СЧ
1—1
00
0 Ö
о
СЧ
1
СЧ CO СЧ СЧ
г
CO CO
Table 6: Roman domination numbers for the direct products Pn X Ck and Cn X Ck, k = 3,..., 9 and
n > 2.
CO CD
Jh
CD CO
k	yr(pu x Ck)			7r(C„ X C k )
3	Г Ht 1; Г Ht 1+1;	if n = 1 (mod 3) otherwise	5; Г Ht 1; Г Ht 1 + 1	if n = 3 if n = 1, 3 (mod 3) ; otherwise
	6;	if n = 2		
4	12; 2n;	if n = 5 otherwise		2n
			8;	if n = 3
	2n + 2	if n = 3, 4	2n;	if n = 0 (mod 5)
5	2n + 3	if n = 2, 6, 7	2n + 2;	if n = 1, 4 (mod 5)
	2n + 4	otherwise	2n + 3; 2n + 4;	if n = 2 (mod 5) otherwise
6	Г 8t 1+1; Г 8t 1 +2;	if n = 1 (mod 3) otherwise	Г 8t 1 + 1 Г 8t 1 + 2 f8t 1 ;	; if n = 1, 4 (mod 6) ; if n = 2 (mod 6) otherwise
	3n + 2	if n = 3, 4, 5		
7	3n + 3 3n + 4	if n = 6, 7 otherwise		
	12	if n = 2		
8	24; 4n;	if n = 5 otherwise		4n
	14	if n = 3		
9	4n + 2;	if n = 1 (mod 3)		
	4n + 3; 4n + 4;	if n = 0 (mod 3) otherwise		
a
CD Jh
i—l O
CSI
1—1
00
0 Ö
o
CSI
1
CSI
co
CSI
сч
£ со со
Table 7: Independent domination numbers for PnüPfc and CnüPfc, k = 2,..., 8 and n > 2.
i(PnOPk)
i(CnDPk )
2	]] ; if n = 1 (mod 2) |"n] + 1; otherwise	\n]; if n = 0, 3 (mod 4) [p] +1; otherwise
3	2 if n = 2 [31] ; if n = 1 (mod 2) [3p] +1; otherwise	[31 ]; if n = 0, 3 (mod 4) Г3т1 +1; otherwise
4	n + 1 if n = 2, 3, 5, 6, 9 n; otherwise	n if n = 0 (mod 2) n + 1; otherwise
5	3; if n = 2 4; if n = 3 [6n] ; if n = 1 (mod 5) [ б1 ] +1; otherwise	[] ; if n = 0 (mod 2) [ б1 ] +1; otherwise
6	11; if n = 7 [l]] ; if n = 1, 5 (mod 7) [lOn] +2; if n = 0 (mod 7) |- ion ] + 1; otherwise	[l]] ; if n = 0, 4, 5, 8,10,12 (mod 14) [IP +2; if n = 7 (mod 14) [ In ] + 1; otherwise
7	10; if n = 5 [5n] + 1; if n = 1, 3 (mod 6) |~5p] ; otherwise	7; if n = 3 [5p] + 1; if n = 0 (mod 3) |~5p] ; otherwise
8-14
see [14]
CO CD
Jh
CD CO
Jh
a
CD U
k
О
СЧ
Table 8: Independent domination numbers for PnOCk and CnüCfc, k = 3,..., 10 and n > 2.
1—1
00
0 Ö
о
СЧ
1
СЧ CO СЧ СЧ
£ CO CO
CO CD
Jh
CD CO
k	i(PnaCk )	i(CnüCfc )
3	n	n
4	n	4; if n = 3 n; otherwise
		8; if n = 5
5	n+2	n +1; if n = 4 (mod 5) n + 2; otherwise
	6		if n = 3
6	г 4n 1 3 г 4n 3	3; + 1;	if n = 1 (mod 3) otherwise
	4		if n = 2
	6		if n = 3
7			if n = 4
	г 38 г t 3 г ¥ 3	+ 2; + 3;	if n = 1 (mod 2) otherwise
	4		if n = 2
	6		if n = 3
8			if n = 4
	г 38 г 9n 3 г 9n 3	+ 2; + 1;	if n = 0 (mod 5) otherwise
9			2n + 2
	2n + 2;		if n = 2, 4, 5
10	2n + 3;		if n = 3, 6, 7, 8, 9
	2n + 4;		otherwise
6; 12; г 4n 3 г 4n 3 +
if n = 3 if n = 7
if n = 0, 4 (mod 6) 1; otherwise
12;
if n = 6
г3 +1; if n = 4, 5,13 (mod 14) l"3^] +2; otherwise
8;	if n = 3
г93n 3 ;	if n = 0,4 (mod 10) г3 + 2; if n = 1 (mod 10)
9 n
Hh + 1;
otherwise
Jh
a
CD U
О
сч
я
1—1
00
0 Ö
о
сч
1
сч со сч сч
г
со со
со
CD
CD СО
18		Polona Pavlic and Janez Žerovnik	
Table 9:	Independent domination numbers for Pn		X Pk and Cn X Pk , k = 3,..., 11 and n > 2.
k		i(Pn X Pk)	i(Cn X Pk)
3		n	n
	\ 4n 1;	if n = 0 (mod 3)	\ 11; if n = 0,1, 3 (mod 6)
4	Г 4n 1 + 1	if n = 2 (mod 3)	\4n 1+1; if n = 2, 5 (mod 6)
	\ f 1 +2	otherwise	l"4^] +2; otherwise
	5;	if n = 3	\ 11; if n = 0,1, 3 (mod 6)
5	\ 4n 1 + 1	if n = 2 (mod 3)	\4n 1+1; if n = 2, 5 (mod 6)
	\ f 1 +2	otherwise	l"4^] +2; otherwise
6	\ 1 ; 1 +1; 1 +2;	if n = 2 (mod 6) if n = 3,4, 5 (mod 6) otherwise	\5n 1 + 1; if n = 4 (mod 6) ; otherwise
	7;	if n = 3	12; if n = 4
7	12	; if n = 4	11; if n = 5
	17	; if n = 7	22; if n =10
	2n + 2; otherwise		2n; otherwise
8	2n + 4;	if n = 1 (mod 3)	
	2n + 2;	otherwise	
	\ 7П 1 + 1	if n = 2 (mod 6)	
9	\ 1+3 \ 7П1 +2	if n = 1 (mod 6) otherwise	
	16;	if n = 4	
10	\ ¥1+2; \ ¥1 +3;	if n = 0, 2 (mod 3) otherwise	
	11;	if n = 3	
11	\ ¥ 1+2	if n = 2 (mod 3)	
	\ 1+4 \ ¥ 1 +5	if n = 0 (mod 3) otherwise	
а
CD Jh
О
СЧ
1—1
00
0 Ö
о
СЧ
1
СЧ CO СЧ СЧ
г
CO CO
CO CD
Jh
CD CO
Table 10: Independent domination numbers for Pn X Ck and Cn X Ck, k = 2,..., 10 and n > 2.
k		i(P? X Ck)		i(C? X Ck)	
3	\ ¥ 1 \ ¥ 1 +	; 1;	if n = 2 (mod 3) otherwise	\ n;1 \ 2? 1; \ ¥ 1 + 1	if n = 3,4, 5 if n = 0 (mod 3) otherwise
	\ 4? 1	;	if n = 0 (mod 3)	\ 4? 1;	if n = 0 (mod 3)
4	\ 4? 1 +	1;	if n = 2 (mod 3)	\ 4? 1 + 1	if n = 1 (mod 3)
	Г4?! +2;		otherwise	\ 4? 1 +2	otherwise
		4;	if n = 2	5;	if n = 3
		5;	if n = 3	8;	if n = 6
5		8;	if n = 5	n + 2;	if n = 2 (mod 5)
		9;	if n = 6	n + 4;	if n = 4 (mod 5)
	n	+ 4;	otherwise	n + 3;	otherwise
\4? 1+1; if n = 2 (mod 3) |~4?~| +2; otherwise
m ;
Г4? 1 + 1; Г4Р1 +2;
if n = 0 (mod 3) if n = 1 (mod 3) otherwise
10;
if n = 4
10
14
[5p] +1; if n = 2 (mod 3)
3
[5p] +2; otherwise
18; \ 5? 1 [5? 1 +1;
if n = 4
if n = 7
if n =10
if n = 0 (mod 3)
otherwise
8	12; 2n + 2;	if n = 4 otherwise
	2n + 2; if	n = 2 (mod 3)
9	2n + 3; if	n = 0 (mod 3)
	2n + 4; otherwise	
10	2n + 4; 2n + 6; 2n + 8;	if n = 2, 3 if n = 5, 6 otherwise
U
a
CD U
6
7
О
сч
я
1—1
00
0 Ö
о
сч
1
сч со сч сч
г
со со
References
CO CD
Jh
CD CO
и
a
CD U
[1]	Alanko, S., Crevals, S., Isopoussu, A., OstergArd, P., and Pettersson, V. Computing the domination number of grid graphs. The Electronic Journal of Combinatorics 18 (2011).
[2]	Allan, R. B., and Laskar, R. On domination and independent domination numbers of a graph. Discrete mathematics 23, 2 (1978), 73-76.
[3]	Babic, D., Graqvac, A., Mohar, B., and Pisanski, T. The matching polynomial of a polygraph. Discrete Applied Mathematics 15 (1986), 11-24.
[4]	Baccelli, F., Cohen, G., and Olsder, G. J. Synchronization and Linearity. Wiley, 2001.
[5]	Bange, D. W., Barkauskas, A. E., Host, L. H., and Slater, P. J. Generalized domination and efficient domination in graphs. Discrete Mathematics 159, 1-3 (1996), 1-11.
[6]	Behzad, A., Behzad, M., and Praeger, C. E. Fundamental dominations in graphs. Bulletin of the institute of combinatorics and its applications 61 (2011), 6-16.
[7]	Bouznif, M., Mqncel, J., and Preissmann, M. Generic algorithms for some decision problems on fasciagraphs and rotagraphs. Discrete mathematics 312 (2012), 2707-2719.
[8]	Burger, A. P., Cockayne, E. J., Grundlingh, W. R., Mynhardt, C. M., Winterbach, W., and van Vuuren, J. H. Finite order domination in graphs. Journal of Combinatorial Mathematics and Combinatorial Computing 49 (2004), 159-175.
[9]	CarrE, B. Graphs and networks. Clarendon Press, Oxford, 1979.
[10]	Chang, T. Y., Clark, W. E., and Hare, E. O. Domination numbers of complete grid graphs, I. Ars Combinatoria 38 (1994), 97-111.
[11]	ChErifi, R., Gravier, S., Lagraula, X., Payan, C., and Zighem, I. Domination number of the cross product of paths. Discrete Applied Mathematics 94 (1999), 101139.
[12]	Cockayne, E. J., Dreyer, P. A., Hedetniemi, S. M., and Hedetniemi, S. T. Roman domination in graphs. Discrete Mathematics 278 (2004), 11-22.
[13]	Cockayne, E. J., Hare, E. O., Hedetniemi, S. T., and Wymer, T. Bounds for the domination number of grid graphs. Congressus Numerantium 47 (1985), 217-228.
[14]	Cortes, M. Independence domination numbers of complete grid graphs. PhD thesis, University of Colorado, 1994.
[15]	El-Zahar, M., Gravier, S., and KlobuCar, A. Note on the total domination number of cross products of graphs. Discrete Mathematics 308 (2008), 2025-2029.
[16]	Fisher, D. C. The domination number of complete grid graphs. 1993.
[17]	Goncalves, D., Pinlou, A., Rao, M., and Thomasse, S. The domination number of grids. SIAM Journal on Discrete Mathematics 25, 3 (2011), 1443-1453.
[18]	Gravier, S. Total domination number of grid graphs. Discrete Applied Mathematics 121 (2002), 119-128.
[19]	Gravier, S., and Mollard, M. Note on domination numbers of Cartesian product of paths. Discrete Applied Mathematics 80 (1997), 247-250.
[20]	Haynes, T. W., Hedetniemi, S. T., and Slater, P. J. Domination in graphs: Advanced topics. Marcel Dekker, New York, 1998.
[21]	Haynes, T. W., Hedetniemi, S. T., and Slater, P. J. Fundamentals of domination in graphs. Marcel Dekker, New York, 1998.
[22]	Henning, M. A. Defending the roman empire from multiple attacks. Discrete Mathematics 271 (2003), 101-115.
[23]	Henning, M. A. A survey of selected recent results on total domination in graphs.
О
СЧ
1—1
00
0 Ö
о
СЧ
1
СЧ CO СЧ СЧ
г
CO CO
[24
[25 [26 [27 [28 [29 [30 [31
[32 [33
[34 [35 [36 [37 [38 [39 [40 [41 [42
Discrete Mathematics 309 (2009), 32-63.
Juvan, M., Mqhar, B., Graqvac, A., KlavZar, S., and Zerovnik, J. Fast computation of the wiener index of fasciagraphs and rotagraphs. Journal of Chemical Information and Computer Sciences 35 (1995), 834-840.
Juvan, M., Mqhar, B., and ZER0VNIK, J. Distance-related invariants on polygraphs. Discrete Applied Mathematics 80 (1997), 57-71.
KlavZar, S., and ZER0VNIK, J. Algebraic approach to fasciagraphs and rotagraphs. Discrete Applied Mathematics 68 (1996), 93-100.
KlqbuZar, A. Domination numbers of cardinal products. Mathematica Slovaca 49, 4 (1999), 387-402.
KlqbuZar, A. Domination numbers of cardinal products P6 x Pn. Mathematical Communications 4 (1999), 241-250.
Klobučar, A. Total domination number of Cartesian products. Mathematical Communication 9 (2004), 35-44.
Klobučar, A. Independent sets and independent dominating sets in the strong product of paths and cycles. Mathematical Communications 10 (2005), 23-30. Kraner čUMENJAK, T., PavliZ, P., and Tepeh, A. On the Roman domination in the lexicographic product of graphs. Discrete Applied Mathematics 160 (2012), 2030-2036.
Livingston, M., and Stout, Q. F. Constant time computation of minimum dominating sets. Congressus Numerantium 105 (1994), 116-128.
Nowakowski, R. J., AND Rall, D. F. Associative graph products and their independence, domination and coloring numbers. Discussiones Mathematicae. Graph Theory 16 (1996), 53-79.
PavliZ, P., AND /Zerovnik, J. A note on the domination number of the Cartesian products of paths and cycles. Submitted. www.imfm.si/preprinti/PDF/01167.pdf. PavliZ, P., AND Zerovnik, J. Roman domination number of the Cartesian products of paths and cycles. The Electronic Journal of Combinatorics 16, 3 (2012), P19. Pisanski, T., Shawe-Taylqr, J., AND Vrabec, J. Edge-colorability of graph bundles. Journal of Combinatorial Theory 35, Series B (1983), 12-19. Rall, D. F. Total domination in categorical products of graphs. Discussiones Mathematicae 25 (2005), 35-44.
Spalding, A. Min-Plus algebra and graph domination. PhD thesis, University of Colorado, 1998.
Yero, I. G., and Rodriguez-Velazquez, J. A. Roman domination in Cartesian product graphs and strong product graphs. manuscript, 2011.
Zerovnik, J. Deriving formulas for domination numbers of fasciagraphs and rotagraphs. Lecture Notes in Computer Science 1684 (1999), 559-568. Zerovnik, J. New formulas for the pentomino exclusion problem. Australasian Journal of Combinatorics 36 (2006), 197-212.
Zmazek, B., AND ^ZEROVNIK, J. On domination numbers of graph bundles. Journal of Applied Mathematics and Computing 22, 1-2 (2006), 39-48.
CO CD
CD CO
и
a
CD U