Article in volume
Authors:
Cafer Caliskan
Antalya Bilim University, Department of Computer Engineering, 07190, Antalya, Turkey
Primoz Šparl
University of Ljubljana, Faculty of Education, Kardeljeva ploscad 16, 1000 Ljubljana
email: primoz.sparl@pef.uni-lj.si
Title:
Efficient domination in Cayley graphs of generalized dihedral groups
PDFSource:
Discussiones Mathematicae Graph Theory 42(3) (2022) 823-841
Received: 2019-09-27 , Revised: 2020-02-04 , Accepted: 2020-02-06 , Available online: 2020-03-02 , https://doi.org/10.7151/dmgt.2309
Abstract:
An independent subset $D$ of the vertex set $V$ of the graph $Γ$ is an
efficient dominating set for $Γ$ if each vertex $v \in V \setminus D$
has precisely one neighbour in $D$. In this article, we classify the connected
cubic Cayley graphs on generalized dihedral groups which
admit an efficient dominating set.
Keywords:
efficient domination set, Cayley graph, generalized dihedral group
References:
- B. Alspach and M. Dean, Honeycomb toroidal graphs are Cayley graphs, Inform. Process. Lett. 109 (2009) 705–708.
https://doi.org/10.1016/j.ipl.2009.03.009 - D.W. Bange, A.E. Barkauskas and P.J. Slater, Efficient dominating sets in graphs, in: Appl. Discrete Math., R.D. Ringeisen and F.S. Roberts (Ed(s)), (Philadelphia, SIAM 1988) 189–199.
- N. Biggs, Perfect codes in graphs, J. Combin. Theory Ser. B 15 (1973) 289–296.
https://doi.org/10.1016/0095-8956(73)90042-7 - W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I. The user language, J. Symbolic Comput. 24 (1997) 235–265.
https://doi.org/10.1006/jsco.1996.0125 - A. Brandstädt, V. Giakoumakis and M. Milanič, Weighted efficient domination for some classes of $H$-free and of $(H_1, H_2)$-free graphs, Discrete Appl. Math. 250 (2018) 130–144.
https://doi.org/10.1016/j.dam.2018.05.012 - C. Caliskan, Š. Miklavič and S. Özkan, Domination and efficient domination in cubic and quartic Cayley graphs on abelian groups, Discrete Appl. Math. 271 (2019) 15–24.
- H.-J. Cho and L.-Y. Hsu, Generalized honeycomb torus, Inform. Process. Lett. 86 (2003) 185–190.
https://doi.org/10.1016/S0020-0190(02)00507-0 - I.J. Dejter and O. Serra, Efficient dominating sets in Cayley graphs, Discrete Appl. Math. 129 (2003) 319–328.
https://doi.org/10.1016/S0166-218X(02)00573-5 - Y.-P. Deng, Efficient dominating sets in circulant graphs with domination number prime, Inform. Process. Lett. 114 (2014) 700–702.
https://doi.org/10.1016/j.ipl.2014.06.008 - Y.-P. Deng, Y.-Q. Sun, Q. Liu and H.-C. Wang, Efficient dominating sets in circulant graphs, Discrete Math. 340 (2017) 1503–1507.
https://doi.org/10.1016/j.disc.2017.02.014 - Q. Dong, X. Yang and J. Zhao, Embedding a fault-free Hamiltonian cycle in a class of faulty generalized honeycomb tori, Comput. Electr. Eng. 35 (2009) 942–950.
https://doi.org/10.1016/j.compeleceng.2008.09.005 - Q. Dong, Q. Zhao and Y. An, The Hamiltonicity of generalized honeycomb torus networks, Inform. Process. Lett. 115 (2015) 104–111.
https://doi.org/10.1016/j.ipl.2014.07.011 - R. Feng, H. Huang and S. Zhou, Perfect codes in circulant graphs, Discrete Math. 340 (2017) 1522–1527.
https://doi.org/10.1016/j.disc.2017.02.007 - R. Frucht, A canonical representation of trivalent Hamiltonian graphs, J. Graph Theory 1 (1976) 45–60.
https://doi.org/10.1002/jgt.3190010111 - J. Huang and J.-M. Xu, The bondage numbers and efficient dominations of vertex-transitive graphs, Discrete Math. 308 (2008) 571–582.
https://doi.org/10.1016/j.disc.2007.03.027 - S. Klavžar, I. Peterin and I.G. Yero, Graphs that are simultaneously efficient open domination and efficient closed domination graphs, Discrete Appl. Math. 217 (2017) 613–621.
https://doi.org/10.1016/j.dam.2016.09.027 - M. Knor and P. Potočnik, Efficient domination in cubic vertex-transitive graphs, European J. Combin. 33 (2012) 1755–1764.
https://doi.org/10.1016/j.ejc.2012.04.007 - K.R. Kumar and G. MacGillivray, Efficient domination in circulant graphs, Discrete Math. 313 (2013) 767–771.
https://doi.org/10.1016/j.disc.2012.12.003 - J. Lee, Independent perfect domination sets in Cayley graphs, J. Graph Theory 37 (2001) 213–219.
https://doi.org/10.1002/jgt.1016 - G.M. Megson, X. Liu and X. Yang, Fault-tolerant ring embedding in a honeycomb torus with node failures, Parallel Process. Lett. 9 (1999) 551–561.
https://doi.org/10.1142/S0129626499000517 - N. Obradović, J. Peters and G. Ružić, Efficient domination in circulant graphs with two chord lengths, Inform. Process. Lett. 102 (2007) 253–258.
https://doi.org/10.1016/j.ipl.2007.02.004 - B. Parhami and D.-M. Kwai, A unified formulation of honeycomb and diamond networks, IEEE Trans. Parallel Distrib. Sys. 12 (2001) 74–80.
https://doi.org/10.1109/71.899940 - P. Potočnik, P. Spiga and G. Verret, Cubic vertex-transitive graphs on up to $1280$ vertices, J. Symbolic Comput. 50 (2013) 465–477.
https://doi.org/10.1016/j.jsc.2012.09.002 - T. Tamizh Chelvam and S. Mutharasu, Subgroups as efficient dominating sets in Cayley graphs, Discrete Appl. Math. 161 (2013) 1187–1190.
https://doi.org/10.1016/j.dam.2012.09.005 - X. Yang, D.J. Evans, H.J. Lai and G.M. Megson, Generalized honeycomb torus is Hamiltonian, Inform. Process. Lett. 92 (2004) 31–37.
https://doi.org/10.1016/j.ipl.2004.05.017 - S. Zhou, Total perfect codes in Cayley graphs, Des. Codes Cryptogr. 81 (2016) 489–504.
https://doi.org/10.1007/s10623-015-0169-0
Close