Geodesic
Efficient Domination in Cayley Graphs of Generalized Dihedral Groups
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 823-841.

Voir la notice de l'article provenant de la source Library of Science

An independent subset D of the vertex set V of the graph Γ is an efficient dominating set for Γ if each vertex v ∈ V 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 
@article{DMGT_2022_42_3_a9,
     author = {Caliskan, Cafer and Miklavi\v{c}, \v{S}tefko and \"Ozkan, Sibel and \v{S}parl, Primo\v{z}},
     title = {Efficient {Domination} in {Cayley} {Graphs} of {Generalized} {Dihedral} {Groups}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {823--841},
     publisher = {mathdoc},
     volume = {42},
     number = {3},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a9/}
}
TY  - JOUR
AU  - Caliskan, Cafer
AU  - Miklavič, Štefko
AU  - Özkan, Sibel
AU  - Šparl, Primož
TI  - Efficient Domination in Cayley Graphs of Generalized Dihedral Groups
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 823
EP  - 841
VL  - 42
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a9/
LA  - en
ID  - DMGT_2022_42_3_a9
ER  - 
%0 Journal Article
%A Caliskan, Cafer
%A Miklavič, Štefko
%A Özkan, Sibel
%A Šparl, Primož
%T Efficient Domination in Cayley Graphs of Generalized Dihedral Groups
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 823-841
%V 42
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a9/
%G en
%F DMGT_2022_42_3_a9
Caliskan, Cafer; Miklavič, Štefko; Özkan, Sibel; Šparl, Primož. Efficient Domination in Cayley Graphs of Generalized Dihedral Groups. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 823-841. http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a9/

[1] 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

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

[3] 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

[4] 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

[5] A. Brandstädt, V. Giakoumakis and M. Milanič, Weighted efficient domination for some classes of H-free and of (H1, H2)-free graphs, Discrete Appl. Math. 250 (2018) 130–144. https://doi.org/10.1016/j.dam.2018.05.012

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

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

[8] 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

[9] 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

[10] 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

[11] 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

[12] 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

[13] 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

[14] R. Frucht, A canonical representation of trivalent Hamiltonian graphs, J. Graph Theory 1 (1976) 45–60. https://doi.org/10.1002/jgt.3190010111

[15] 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

[16] 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

[17] 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

[18] 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

[19] J. Lee, Independent perfect domination sets in Cayley graphs, J. Graph Theory 37 (2001) 213–219. https://doi.org/10.1002/jgt.1016

[20] 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

[21] 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

[22] 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

[23] 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

[24] 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

[25] 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

[26] S. Zhou, Total perfect codes in Cayley graphs, Des. Codes Cryptogr. 81 (2016) 489–504. https://doi.org/10.1007/s10623-015-0169-0