Domination Number of Square of Cartesian Products of Cycles

Morteza Alishahi^*, Sakineh Hoseini Shalmaee

Islamic Azad University, Nazarabad Branch.

DOI: 10.4236/ojdm.2015.54008                

Abstract

A set  is a dominating set of G if every vertex of  is adjacent to at least one vertex of S. The cardinality of the smallest dominating set of G is called the domination number of G. The square G² of a graph G is obtained from G by adding new edges between every two vertices having distance 2 in G. In this paper we study the domination number of square of graphs, find a bound for domination number of square of Cartesian product of cycles, and find the exact value for some of them.

Keywords

Domination Number, Square of a Graph, Cartesian Product

1. Introduction

The usual graph theory notions not herein, refer to [1] . The neighborhood of vertex u is denoted by and the close neighborhood of vertex u is denoted by. Let, the neighborhood and closed neighborhood of S are defined as and. If, then. If and,

then. The diameter of G denoted by is defined as . A set is a dominating set of G if every vertex of is adjacent to at least one vertex of S. The cardinality of the smallest dominating set of G, denoted by, is called the domination number of G. A dominating set of cardinality is called a g-set of G [2] . A dominating set S is a minimal dominating set if no proper subset is a dominating set. Given any graph G, its square graph is a graph with vertex set and two vertices are adjacent whenever they are at distance 1 or 2 in G. For example. A set is a 2-distance dominating set of G if or 2 for every vertex of. The cardinality of the smallest 2-distance dominating set of G, denoted by, is called 2-distance domination number of G. Every 2-distance dominating set of G is a

dominating set of, so. The Cartesian product of Graphs G and H denoted by is a

graph with vertex set and the edge set

. The graph is obtained by

locating copies of grpah H instead of vertices of G and connecting the corresponding vertices of to if vertex is adjacent to in G. is isomorphic to. We denote a cycle with n vertices by and a path with n vertices by. The bipartite geraph is named claw.

2. Preliminaries Results

Theorem 1. Let G be a graph. Then

a) If, then.

b) If, then.

Proof. a) Every dominating set of is a dominating set of G so.

b) Every dominating set of G is a dominating set of so.

Theorem 2. [3] A dominating set S is a minimal dominating set if and only if for each vertex, one of the following conditions holds:

a) u is an isolated vertex of S.

b) there exist a vertex for which.

Theorem 3. [3] If G is a graph with no isolated vertices and S is a minimal dominating set of G, then is a dominating set of G.

Proof. Let S be a g-set of G. S is a minimal dominating set of G. By Theorem 3, is a dominating set of G too, so, so.

Theorem 4. [4] If G is a connected claw free graph, then.

Theorem 5. [5] Let G be a graph. Then.

Since, by Theorems 4 and 5 we have the following corollary.

Corollary 6..

Vizing conjecture

Let G and H be two graphs. Then [6] .

3. Domination Number of Square of Graphs

Theorem 7. Let S be a dominating set of. Then S is a minimal dominating set of if and only if each vertex satisfies at least one of the following conditions:

a) There exists a vertex for which.

b) for every vertex.

Proof. If and u does’t satisfy conditions a) and b), then the set is a dominating set of that is contradiction. Conversely, let S be a dominating set of but not minimal. Then there exists a vertex such that is a dominating set of, too. So or 2 for every; therefore S doesn’t satisfy in condition a). In addition or 2, so S doesn’t satisfy in condition b).

Theorem 8. If, then.

Proof. Let. Since, the set is a dominating set of. Therefore.

Theorem 9. If, then, for every.

Proof. Let u be an arbitrary vertex of G. Let. Since, , for every. Therefore is a dominating set of. and, Hence.

Theorem 10. Let G be a graph. Then.

Proof. Let and be the copies of in corresponding to the vertices. Let be a g-set of G. Then the set that contains a vertex of each copies is a g-set of. Since, the result holds.

Theorem 11. For every,.

Proof. The graphs and are complete graphs, therefore. So the result holds for and. Let,. Since, by the Theorem 5 we have. On the other hand by Figure 1 the set is a dominating set of size for. So, therefore.

Theorem 12. For every,.

Proof., and the result holds for these graphs. Let,. Since, by Theorem 5 we have. By Figure 2 the set:

is a dominating set of size for, so; therefore.

Theorem 13. For every, , and for every,.

Proof. The graphs and have mn vertices and every vertex u dominates at least 13 vertices in and (Figure 3), so the result holds.

By Theorem 13, or equals the minimum number of diamonds like Figure 4. we can cover all the vertices of or.

Figure 1. A dominating set of.

Figure 2. A dominating set of.

Figure 3. Dominated vertices by u in and.

Figure 4. Dominated vertices by one vertex in and.

In this paper we use short display or s.d to show the graphs and for simplicity; it means that we don’t draw the edges of these graphs and draw only their vertices.

Theorem 14. For every,.

Proof. By Theorem 13 we have. In Figure 5 that is s.d of. It is determined by a g-set of size 13 for. Therefore; hence.

We can obtain s.d of with dominating set of size 13kt for by locating kt copies of Figure 5 in k rows and t columns. Hence. By Theorem 13 we have

Figure 5. A dominating set of size 13 for.

, so

Theorem 15., for every.

Proof. Since, by Theorem 10 and Corollary 6 we have

Theorem 16., , and

Proof. By Theorem 13 we have. In Figure 6 it is determined by a dominating set of size for, , so for these graphs we have.

In Figure 6, the seventh column of s.d of (from left to right) is similar to the first column of s.d of, and,. By setting s.d of k graphs and one s.d of or or or consecutively from left to right such that the first column of every s.d of graph locates on the last column of s.d of the previous graph, we can obtain a s.d of with a dominating set of size for,. By the same setting for s.d of k graphs we can obtain a s.d of with a dominating set of size for. Also by the same setting for s.d of graphs and one s.d of we can obtain a s.d of with a dominating set of size 2k for.

Theorem 17., , and

Proof. By Theorem 13 we have. In Figure 7 it is determined by a dominating set for

Figure 6. A dominating set for,.

Figure 7. A dominating set for,.

, and,.

By Figure 7 we have,. So for these graphs equality holds.

In Figure 7, the seventh column of s.d of (from left to right) is similar to the first column of s.d of, and,. By setting s.d of k graphs and one s.d of or or consecutively from left to right such that the first column of every s.d of graph locates on the last column of the previous s.d of graph, we can obtain a s.d of with a dominating set of size for,. By the same setting for s.d of k graphs we can obtain a s.d of with a dominating set of size for and by the same setting for s.d of k graphs and one s.d of we can obtain a s.d of with a dominating set of size for. Also by the same setting for s.d of graphs and one s.d of we can obtain a s.d of with a dominating set of size 3k for.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	West, D.B. (2001) Introduction to Graph Theory. 2nd Edition, Prentice-Hall, Upper Saddle River.
[2]	Haynes, T., Hedetniemi, S. and Slater, P.J. (1997) Fundamentals of Domination in Graphs. M. dekker, Inc., New York.
[3]	Ore, O. (1962) Theory of Graphs. American Mathematical Society Colloquium Publications, 38 (American Mathematical Society, Providence, RI).
[4]	Cockayne, E.J., Ko, C.W. and Shepherd, F.B. (1985) Inequalities Concerning Dominating Sets in Graphs. Technical Report DM-370-IR, Department of Mathematics, University of Victoria.
[5]	Walikar, H.B., Acharya, B.D. and Sampathkumar, E. (1979) Recent Developments in the Theory of Domination in Graphs. In MRI Lecture Notes in Math. Mehta Research Institute of Mathematics, Allahabad, Vol. 1.
[6]	Vizing, V.G. (1963) The Cartesian Product of Graphs. Vycisl. Sistemy, 9, 30-43.