Bounds for Domination Parameters in Cayley Graphs on Dihedral Group

ABSTRACT

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

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

Cite this paper

T. Chelvam and G. Kalaimurugan, "Bounds for Domination Parameters in Cayley Graphs on Dihedral Group,"*Open Journal of Discrete Mathematics*, Vol. 2 No. 1, 2012, pp. 5-10. doi: 10.4236/ojdm.2012.21002.

T. Chelvam and G. Kalaimurugan, "Bounds for Domination Parameters in Cayley Graphs on Dihedral Group,"

References

[1] S. Lakshmivarahan, J. S. Jwo and S. K. Dhall, “Symmetry in Interconnection Networks Based on Cayley Graphs of Permutation Groups: A Survey,” Parallel Computing, Vol. 19, No. 4, 1993, pp. 361-407. doi:10.1016/0167-8191(93)90054-O

[2] E. J. Cockayne, R. M. Dawes and S. T. Hedetniemi, “Total Domination in Graphs,” Networks, Vol. 10, No. 3, 1980, pp. 211-219. doi:10.1002/net.3230100304

[3] I. J. Dejter and O. Serra, “Efficient Dominating Sets in Cayley Graphs,” Discrete Applied Mathematics, Vol. 129, No. 2-3, 2003, pp. 319-328. doi:10.1016/S0166-218X(02)00573-5

[4] R J. Huang and J.-M. Xu, “The Bondage and Efficient Domination of Vertex Transitive Graphs,” Discrete Mathe- matics, Vol. 308, No. 4, 2008, pp. 571-582. doi:10.1016/j.disc.2007.03.027

[5] J. Lee, “Independent Perfect Domination Sets in Cayley Graphs,” Journal of Graph Theory, Vol. 37, No. 4, 2000, pp. 219-231.

[6] T. Tamizh Chelvam and I. Rani, “Dominating Sets in Cayley Graphs on Zn,” Tamkang Journal of Mathematics, Vol. 37, No. 4, 2007, pp. 341-345.

[7] T. Tamizh Chelvam and I. Rani, “Independent Domination Number of Cayley Graphs on Zn,” The Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 69, 2009, pp. 251-255.

[8] T. Tamizh Chelvam and I. Rani, “Total and Connected Domination Numbers of Cayley Graphs on Zn,” Advanced Studies in Contemporary Mathematics, Vol. 20, 2010, pp. 57-61.

[9] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, “Fundamentals of Domination in Graphs,” Marcel Dekker, New York, 1998.

[10] K. Conrad, “Dihedral Groups II,” 2009. http://www.math.uconn.edu/~kconrad/blurbs/grouptheory/dihedral2.pdf

[1] S. Lakshmivarahan, J. S. Jwo and S. K. Dhall, “Symmetry in Interconnection Networks Based on Cayley Graphs of Permutation Groups: A Survey,” Parallel Computing, Vol. 19, No. 4, 1993, pp. 361-407. doi:10.1016/0167-8191(93)90054-O

[2] E. J. Cockayne, R. M. Dawes and S. T. Hedetniemi, “Total Domination in Graphs,” Networks, Vol. 10, No. 3, 1980, pp. 211-219. doi:10.1002/net.3230100304

[3] I. J. Dejter and O. Serra, “Efficient Dominating Sets in Cayley Graphs,” Discrete Applied Mathematics, Vol. 129, No. 2-3, 2003, pp. 319-328. doi:10.1016/S0166-218X(02)00573-5

[4] R J. Huang and J.-M. Xu, “The Bondage and Efficient Domination of Vertex Transitive Graphs,” Discrete Mathe- matics, Vol. 308, No. 4, 2008, pp. 571-582. doi:10.1016/j.disc.2007.03.027

[5] J. Lee, “Independent Perfect Domination Sets in Cayley Graphs,” Journal of Graph Theory, Vol. 37, No. 4, 2000, pp. 219-231.

[6] T. Tamizh Chelvam and I. Rani, “Dominating Sets in Cayley Graphs on Zn,” Tamkang Journal of Mathematics, Vol. 37, No. 4, 2007, pp. 341-345.

[7] T. Tamizh Chelvam and I. Rani, “Independent Domination Number of Cayley Graphs on Zn,” The Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 69, 2009, pp. 251-255.

[8] T. Tamizh Chelvam and I. Rani, “Total and Connected Domination Numbers of Cayley Graphs on Zn,” Advanced Studies in Contemporary Mathematics, Vol. 20, 2010, pp. 57-61.

[9] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, “Fundamentals of Domination in Graphs,” Marcel Dekker, New York, 1998.

[10] K. Conrad, “Dihedral Groups II,” 2009. http://www.math.uconn.edu/~kconrad/blurbs/grouptheory/dihedral2.pdf