ABSTRACT

In this paper, sharp upper bounds for the domination number, total domination number and connected domination number for the Cayley graph G = Cay(D_2n, Ω) constructed on the finite dihedral group D_2n, and a specified generating set Ω of D_2n. Further efficient dominating sets in G = Cay(D_2n, Ω) are also obtained. More specifically, it is proved that some of the proper subgroups of D_2n are efficient domination sets. Using this, an E-chain of Cayley graphs on the dihedral group is also constructed.

1. Introduction and Notation

Design of interconnection networks is an important integral part of any parallel processing of distributed system. There has been a strong interest recently in using Cayley graphs as a model for developing interconnection networks for large interacting arrays of CPU’s. An excellent survey of interconnection networks based on Cayley graphs can be found in [1]. The concept of domination for Cayley graphs has been studied by various authors [2-7]. I. J. Dejter and O. Serra [3] obtained efficient dominating sets for Cayley graphs constructed on a class of groups containing permutation groups. The efficient domination number for vertex transitive graphs has been obtained by Jia Huang and Jun-Ming Xu [4]. A necessary and sufficient condition for the existence of an independent perfect domination set in Cayley graphs has been obtained by J. Lee [5]. Total domination in graphs was introduced by Cockayne, Dawes, and Hedetniemi [2] and is now well studied in graph theory. T. Tamizh Chelvam and I. Rani [6-8] have obtained bounds for various domination parameters for a class of Circulant graphs.

Let Γ be a finite group. Let Ω be a generating set of Γ satisfying e Ï Ω and a Î Ω implies a⁻¹ Î Ω. The Cayley graph corresponding to Γ is the graph G = (V, E), where V(G) = Γ and E(G)={(x, xa): x Î V(G), a Î Ω} and it is denoted by G = Cay(Γ, Ω). Let G= (V, E), be a finite, simple and undirected graph. We follow the terminology of [9]. A set S Í V of vertices in a graph G is called a dominating set if every vertex v Î V is either an element of S or adjacent to an element of S. A dominating set S is a minimal dominating set if no proper subset of S is a dominating set. The domination number g(G) of a graph G is the minimum cardinality of a dominating set in G and the corresponding dominating set is called a g-set. A set S Í V is called a total dominating set if every vertex v Î V is adjacent to an element u (¹v) of S. The total domination number g_t(G) equals the minimum cardinality among all the total dominating sets in G and the corresponding total dominating set is called a g_t-set. A dominating set S is called a connected dominating set if the induced subgraph áSñ is connected. The connected domination number g_c(G) of a graph G equals the minimum cardinality of a connected dominating set in G and a corresponding connected dominating set is called a g_c-set. A set S Í V is called an efficient dominating set (E-set) if for every vertex v Î V, |N[v]∩S|=1.

An E-chain is a countable family of nested graphs, each of which has an E-set. We say that a countable family of graphs G = {G_i, i ³ 1} with each G_i has an E-set S_i is an inclusive E-chain if for every i ³ 1, there exists a surjective map f_i: G_i+1 ® G_i such that (S_i) Ì S_i+1. And also we define that a finite family of graphs G = {G_i, i ³ 0} is an inductive E-chain if every G_i+1 is a spanning subgraph of G_i and each G_i has an E-set S_i. Let V(G_i) be any finite group and if, for each i ³ 0, there exists a bijective map z_i: V(G_i) ® V(G_i+1) such that z_i(S_i ) Í S_i+1 and S_i is the subgroup of V(G_i) then we say that G is an inductive subgroups E-chain.

A graph is called a covering of G with projection if there is a surjection such that is a bijection for any vertex and. We use the covering function to show the inclusive E-chain.

In this paper, we obtain upper bounds for domination number, total domination number and connected domination number in a Cayley graph constructed on the dihedral group, for and a generating set. Further, we obtain some E-sets in. Note that the dihedral group with identity e is the group generated by two elements r and s with and. From these defining relations, one can take

and

, where is a generating set of. Throughout this paper, be an integer, ,

and k, t be integers such that

. We take the generating set in the form that

where and Let for, for and. Some of the results are listed below for further reference.

Theorem 1 [4] Let G be a k-regular graph. Then

, with the equality if and only if G has an efficient dominating set.

Theorem 2 [5] Let be a covering and let S be a perfect domination set of G. Then is a perfect domination set of. Moreover, if S is independent, then is independent.

Theorem 3 [10] Every subgroup of the dihedral group is cyclic or dihedral. A complete listing of the subgroups is as follows:

1) cyclic subgroups, where d divides n, with index 2d.

2) dihedral subgroups, where d divides n and with index d. Every subgroup of occurs exactly once in this listing.

2. Domination, Total Domination and Connected Domination Numbers

In this section, we obtain upper bounds for the domination number, total domination number and connected domination number of graph. Also whenever the equality occurs we give the corresponding sets.

Lemma 4 Let be an integer, and kt are integers such that. Let

and. If for , for and , then

.

Proof. Let and. Consider the set

Clearly and

where and We have to prove that. If, then we can write as either one vertex of the form or, where. By the division algorithm, , where and.

Suppose. We have the following cases:

Case 1. Suppose and.

Subcase 1.1 If, then by the definition of.

Subcase 1.2 If, for some integers m, g with and then whereas and so.

Case 2. Suppose and . In this case, there exists an integer h with such that

Subcase 2.1 If then

Subcase 2.2 Suppose, for some integers m, g with and. In this case, , which means that

Case 3. Suppose and

.

In this case, there exists an integer h with such that.

Subcase 3.1 If, then .

Subcase 3.2 Suppose, for some integers m, g, with and. In this case, , which means that .

Case 4. Suppose and

.

Then there exists an integer h with such that.

Subcase 4.1 If, then.

Subcase 4.2 Suppose, for some integers m, g with and. In this case, which means that.

Suppose. We have the following cases:

Case 1. Suppose and . In this case, there exists an integer h with such that

Subcase 1.1 If, then.

Subcase 1.2 Suppose, for some integers m, g with and. In this case, , which means that.

Case 2. Suppose and . In this case, there exists an integer h with such that .

Subcase 2.1 If then .

Subcase 2.2 Suppose, for some integers m, g with and. In this case, , which means that .

Case 3. Suppose and . In this case, there exists an integer h with such that.

Subcase 3.1 If, then by the definition of  .

Subcase 3.2 Suppose, for some integers m, g with and. In this case, , which means that .

Thus S is a dominating set of G.

The following lemma provides an upper bound for the total domination number in.

Lemma 5 Let be an integer, and k, t be integers such that. Let

and. If for

, for and

, then.

Proof. Let and. Consider the set

.

Clearly. We have to prove that If, then we can write as either one vertex of the form or, where. By the division algorithm, , where and. We have the following cases:

Case 1. Suppose and. For some integer g with and by the definition of d, if, then or if

, then.

Case 2. Suppose and. We can write, for some integers m, g with and. If, then whereas and so or if, then

whereas and so

.

Case 3. Suppose and

. In this case, there exists an integer h with such that or

.

Subcase 3.1 Suppose and if, then or ifthen.

Subcase 3.2 Suppose, for some integers m, g with and. In this case, if, then, which means that

or if, then

, which implies that .

Case 4. Suppose and. Then there exists an integer h with such that or.

Subcase 4.1 When, and if, then or if, then

.

Subcase 4.2 Suppose, for some integers m, g with and. In this case, if and, which means that

or if, then

, which means that .

Thus is a total dominating set of G. .

Now we obtain an upper bound for the connected domination number.

Lemma 6 Let be an integer, and k, t be integers such that. Let

and. If for, for and

, then.

Proof. Let and. Consider the set

.

In the notation of Lemma 5, a₁ = 1 and and is a total dominating set. Since and for each with, we have paths

and . Also note that and, and are connected. Hence the induced subgraph is connected.

3. Subgroups as Efficient Domination Sets

In this section, we obtain some E-sets in . Moreover we have identified certain subgroups of which are also efficient domination sets in.

Theorem 7 Let be an integer, and k, t be integers such that and d is an integer such that divides n. Let

and. Then. In this case, has an E-set.

Proof. Let and. In the notation of Lemma 4,’s and’s are same, for all and for all.

Let and. By Lemma 4,

is a dominating set and hence. Since

is regular, by Theorem 1, one can conclude that is an E-set in.

Remark 8 Note that Theorem 3 identifies all subgroups of the dihedral group. Now we us identify some of the subgroups as efficient dominating sets.

Theorem 9 Let be an integer, and k, t be integers such that, and divides. Let be a subgroup of the dihedral group, where and, Then, there exists a generating set of such that H is an efficient dominating set for the Cayley graph.

Proof. Let

and. By taking in Theorem 7,

is an efficient dominating set of.

Remark 10 Under the assumptions of Theorem 9, is an efficient dominating set for the Cayley graph for all.

4. E-Chains in Cayley Graphs

Theorem 7 and 9 provide a tool to produce E-sets and visualize some of the subgroups as E-sets in . We use this tool to obtain an inclusive E-chain and inductive subgroups E-chain of Cayley graphs on the dihedral group.

Theorem 11 Let be an integer,

and k be an integers such that, ,

and Assume that divides and divides. Then the finite family of graphs is inductive subgroups E-chain.

Proof. Let. By the assumption. divides. Define the map by for all. By Theorem 9, has an efficient dominating set and it is of the form

and also’s are subgroups. It implies that for every. Hence the family of graphs is inductive subgroups E-chain.

The construction of an inclusive E-chain of Cayley graphs is based on the following lemma.

Lemma 12 Let be an integer, , k, t be integers such that, and d is an integer such that divides. For, let

and. Then is a covering of.

Proof. Define the surjective map

by and

for all j, where. Note that is a group homomorphism from onto. Let. Suppose and are adjacent in. Then, there exists with

or with such that

or. Since is a group homomorphism and

, we have or and so and are adjacent in. Consider the map for any vertex and. Claim is bijection. Any element in as either one vertex of the form or, where. Let Then we have following three cases:

Case 1. Let and with. Suppose, i.e. . i.e. which is a contradiction to. Therefore.

Case 2. Let and. Suppose

, i.e. This means

or, which is a contradiction. Therefore.

Case 3. Let and with. Suppose, i.e.

. i.e.

which is a contradiction. Therefore . Hence distinct elements of are distinctly mapped onto and so is a required bijection.

Theorem 13 Let be an integer, k, t, be integers such that, and d is an integer such that divides. For let

and. Let be an efficient dominating set for. Then the finite family of graphs is an inclusive E-chain.

Proof. Since by above Lemma, is a covering of. Since by Theorem 2,. Hence the finite family of graphs   is an inclusive E-chain.

5. Acknowledgements

The work reported here is supported by the Special Assistance Programme (F510-DRS-I/2007) of University Grants Commission, India awarded to the Department of Mathematics, Manonmaniam Sundaranar University for the period 2007-2012.

REFERENCES