# Domination numbers of the complete grid graphs [P.sub.k] x [P.sub.n]/ Numeros de dominacao de graficos grid completos [P.sub.k] x [P.sub.n].

IntroductionA dominating set in a graph is a set of vertices having the property that every vertex not in the set is adjacent to a vertex in the set. The domination number [gamma](G) of a graph G is the cardinality of a smallest dominating set in G.

The problem of finding the domination number of a arbitrary grid graph (= subgraph of [P.sub.k] x [P.sub.n]) is NP-complete (CLARK et al., 1990).

In this paper, we introduce the concept of transforming the domination from a vertex in a dominating set D of a graph G = (V, E) to a vertex in V - D, where G is a simple connected graph. We give an algorithm using this transformation to obtain a dominating set of a graph G.

A graph G = (V, E) is a mathematical structure which consists of two sets V and E, where V is finite and nonempty, and every element of E is an unordered pair {u, v} of distinct elements of V; we simply write uv instead of {u, v}.

The elements of V are called vertices, while the elements of E are called edges (BONDY; MURTY, 2008).

Two vertices u and v of a graph G are said to be adjacent if uv [member of] E.

The neighborhood of v is the set of all vertices of G which are adjacent to v; the neighborhood of v is denoted by N(v). The closed neighborhood of v is [bar.N] (v), [bar.N] (v) = N (v) [union] {v}.

The degree d (v) of a vertex v is the cardinality [absolute value of N (v)], d (v) = [absolute value of N (v)].

Material and methods

Definitions

Let D be a dominating set of a graph G = (V, E).

1. We define the function CD, which we call the weight function, as follows: [C.sub.D]: V [right arrow] N, where N is the set of natural numbers, [C.sub.D](v) = [absolute value of [??](v)], where [??](v) = {w [member of] D: vw [member of] E or w = v}.

1. e. the weight of v is the number of vertices in D which dominate v.

2. We say that v [member of] D has a moving domination if there exists a vertex w [member of] N (v) - D such that wu [member of] E for every vertex u, u [member of] {x [member of] N(v): [C.sub.D](x) = 1}.

3. We say that a vertex veD is a redundant vertex of D if [C.sub.D] (w) [greater than or equal to] 2 for every vertex w [member of] [bar.N] (v).

4. If v [member of] D has a moving domination, we say that v is inefficient if transforming the domination from v to any vertex in N(v) would not produce any redundant vertex.

Complete grid graph [P.sub.k] x [P.sub.n]:

For two vertices [v.sub.o] and [v.sub.n] of a graph G, a [v.sub.o] - [v.sub.n] walk is an alternating sequence of vertices and edges [v.sub.o], [e.sub.1], [v.sub.1], ..., [e.sub.n], [v.sub.n] such that consecutive vertices and edges are incident.

A path is a walk in which no vertex is repeated. A path with n vertices is denoted by [P.sub.n], it has n - 1 edges; the length of [P.sub.n] is n - 1; the cartesian product [P.sub.k] x [P.sub.n] of two paths is the complete grid graph with vertex set V = {(i, j): 1 [less than or equal to] i [less than or equal to] k, 1 [less than or equal to] j [less than or equal to] n} where ([u.sub.1], [u.sub.2]) ([v.sub.1], [v.sub.2]) is a edge of [P.sub.k] x [P.sub.n] if [absolute value of [u.sub.1] - [v.sub.1]] + [absolute value of [u.sub.2] - [v.sub.2]] = J (CHANG; CLARK, 1993).

If D is a dominating set of [P.sub.k] x [P.sub.n] which has no redundant vertex, then a vertex v [member of] D has a moving domination if and only if one of the following two cases occurs:

Case (1): for every vertex w [member of] N(v), we have [C.sub.D] (w) [greater than or equal to] 2.

In this case, the domination of v can be transformed to any vertex in N(v) - D.

Case(2): there exists exactly one vertex u [member of] N(v) such that [C.sub.D](u) = 1 in this case, the domination of v can be transformed only to u.

An algorithm for finding a dominating set of a graph [P.sub.k] x [P.sub.n] using a transformation of domination of vertices

1. Let [P.sub.k] x [P.sub.n] = (V, E) be a graph of order greater than J; [absolute value of V] = m.

2. Let D = V be a dominating set of [P.sub.k] x [P.sub.n]. then, for any vertex v [member of] D we have [C.sub.D](v) = d(v) + 1 [greater than or equal to] 2.

3. Pick a vertex [v.sub.1] of D, and delete from D all

vertices w, w [member of] N([v.sub.1]) then, for 1 < n [m/2], pick a [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and delete from D all vertices [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

4. If D contains a redundant vertex, then delete it.

Repeat this process until D has no redundant vertex.

5. Transform domination from vertices of D which have moving domination to vertices in V - D to obtain redundant vertices and go to step 4.

If no redundant vertex can be obtained by a transformation of domination of vertices of D, then stop, and the obtained dominating set D satisfies:

for every v [member of] D, [there exists] w [member of] [bar.N](v) such that [C.sub.D](w) = 1.

Example

J. Let (k, n) be the vertex in the k - th row and in the n - th column of the graph G = [P.sub.7] x [P.sub.16]; [absolute value of V] = 112.

2. Let D = V, dominating set of G.

3. Pick a vertex [v.sub.1] = (2,1) [member of] D, and delete from D all vertices w, w [member of] N([v.sub.1]), then, for 1 < n < [112/2], pick a vertex [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and delete from D all vertices w, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We obtain the dominating set D (black circles) in figure 1.

[FIGURE 1 OMITTED]

4. Since for every vertex v [member of] D, [there exists]w [member of] [bar.N](v) such that [C.sub.D](w) = 1, D has no redundant vertices.

5. Transform the domination from the vertex (6, J6) to the vertex (5, J6) and delete, from D, the resulting redundant vertex (5, J5).

Therefore, the set D indicated in figure 2 (black circles) is a dominating set of G = [P.sub.7] x [P.sub.16].

Note that D minimum dominating set (see CHANG et al., 1994) [gamma]([P.sub.7] X [P.sub.16]) = 27 .

[FIGURE 2 OMITTED]

And so, we gradually get domination numbers of [P.sub.7] x [P.sub.n].

[GRAPHIC OMITTED]

[GRAPHIC OMITTED]

[GRAPHIC OMITTED]

[GRAPHIC OMITTED]

[GRAPHIC OMITTED]

[GRAPHIC OMITTED]

[GRAPHIC OMITTED]

[GRAPHIC OMITTED]

[GRAPHIC OMITTED]

[GRAPHIC OMITTED]

[GRAPHIC OMITTED]

[GRAPHIC OMITTED]

Table 1. Domination numbers [gamma]([P.sub.7] x [P.sub.n]), n [greater than or equal to] 1.

Hence:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where t is a positive integer.

Dominating sets for [P.sub.8] x [P.sub.n] Grid graph

By self-method, we give in Table 2, [gamma]([P.sub.8] x [P.sub.n]), n [greater than or equal to] 1.

[GRAPHIC OMITTED]

And by gradually, we find that: [gamma]([P.sub.8] X [P.sub.n]) = 2n for 6 [less than or equal to] n [less than or equal to] 14.

[GRAPHIC OMITTED]

And by gradually, we find that [gamma]([P.sub.8] x [P.sub.n]) = 2n - 1 for 15 [less than or equal to] n [less than or equal to] 22.

[GRAPHIC OMITTED]

And by gradually, we find that [gamma]([P.sub.8] x [P.sub.n]) = 2n - 2 for 23 [less than or equal to] n [less than or equal to] 30.

[GRAPHIC OMITTED]

And by gradually, we find that [gamma]([P.sub.8] x [P.sub.n]) = 2n - 3 for 31 [less than or equal to] n [less than or equal to] 38.

[GRAPHIC OMITTED]

And by gradually, we find that [gamma]{[P.sub.8] x [P.sub.n]) = 2n - 4 for 39 [less than or equal to] n [less than or equal to] 46.

Hence:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where t is a integer.

Table 2. Domination numbers [gamma]([P.sub.8] x [P.sub.n]), n [greater than or equal to] 1.

Dominating sets for [P.sub.9] x [P.sub.n] Grid graph

By self-method, we give in Table 3, [gamma]([P.sub.9] x [P.sub.n]), n [greater than or equal to] 1

[GRAPHIC OMITTED]

And by gradually, we find that [gamma]([P.sub.9] x [P.sub.n]) = 2n + 2 for 4 [less than or equal to] n [less than or equal to] 12.

[GRAPHIC OMITTED]

And by gradually, we find that y([P.sub.9] x [P.sub.n]) = 2n + 3 for 13 [less than or equal to] n [less than or equal to] 23.

[GRAPHIC OMITTED]

And by gradually, we find that [gamma]([P.sub.9] x [P.sub.n]) = 2n + 4 for 24 [less than or equal to] n [less than or equal to] 34.

Hence:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where t is a integer.

Table 3. Domination numbers y(P9 X [P.sub.n] ), n [greater than or equal to] 1.

We plan to deal with [P.sub.k] x [P.sub.n] grid graphs, for n [greater than or equal to] 1 and k [greater than or equal to] 10.

Results and discussion

[TABLE 1 OMITTED]

[TABLE 2 OMITTED]

[TABLE 3 OMITTED]

Conclusion

From these results, we note that it is possible to calculate the domination numbers quickly and without the need of a calculator in most cases, however the results published previously, you must necessarily use a calculator.

We tried this method on large grid graphs, and we obtained similar results quickly

Doi: 10.4025/actascitechnol.v34i3.11636

References

BONDY, J. A.; MURTY, U. S. R. Graph theory, Springer, 2008.

CHANG, T. Y.; CLARK, W. E. The domination numbers of 5 x n and 6 x n grid graphs. Journal of Graph Theory, v. 17, n. 1, p. 81-107, 1993.

CHANG, T. Y.; CLARK, W. E.; HARE, E. O. Domination numbers of complete grid graph, I. Ars Combinatoria, v. 38, p. 97-111, 1994.

CLARK, B. N.; COLBOURN, C. J.; JOHNSON, D. S. Unit disk graphs. Discrete Math, v. 86, n. 1, p. 165-177, 1990.

Received on November 6, 2010.

Accepted on October 14, 2011.

License information: This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Mahmoud Saoud

Ecole Normale Superieure, Departement de mathematiques, BP 92 Kouba, 16050,

Alger, Algerie. E-mail: saoud_m@yahoo.fr