Bounds for Domination Parameters in Cayley Graphs on Dihedral Group
T. Tamizh Chelvam, G. Kalaimurugan
DOI: 10.4236/ojdm.2012.21002   PDF    HTML   XML   4,600 Downloads   10,666 Views   Citations


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.

Share and Cite:

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.

Conflicts of Interest

The authors declare no conflicts of interest.


[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.

Copyright © 2023 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.