Perfect directed codes in Cayley digraphs

Yan Wang; Kai Yuan; Ying Zhao; Yan Wang; Kai Yuan; Ying Zhao

doi:10.3934/math.20241160

AIMS Mathematics

2024, Volume 9, Issue 9: 23878-23889. doi: 10.3934/math.20241160

Previous Article Next Article

Research article Special Issues

Perfect directed codes in Cayley digraphs

School of Mathematics and Information Science, Yantai University, Yan Tai, China

Received: 24 May 2024 Revised: 07 August 2024 Accepted: 08 August 2024 Published: 12 August 2024
MSC : 05C20, 05C25, 05C69

A perfect directed code (or an efficient twin domination) of a digraph is a vertex subset where every other vertex in the digraph has a unique in- and a unique out-neighbor in the subset. In this paper, we show that a digraph covers a complete digraph if and only if the vertex set of this digraph can be partitioned into perfect directed codes. Equivalent conditions for subsets in Cayley digraphs to be perfect directed codes are given. Especially, equivalent conditions for normal subsets, normal subgroups, and subgroups to be perfect directed codes in Cayley digraphs are given. Moreover, we show that every subgroup of a finite group is a perfect directed code for a transversal Cayley digraph.
- Cayley digraph,
- perfect directed code,
- efficient twin domination
Citation: Yan Wang, Kai Yuan, Ying Zhao. Perfect directed codes in Cayley digraphs[J]. AIMS Mathematics, 2024, 9(9): 23878-23889. doi: 10.3934/math.20241160

Related Papers:

Abstract

A perfect directed code (or an efficient twin domination) of a digraph is a vertex subset where every other vertex in the digraph has a unique in- and a unique out-neighbor in the subset. In this paper, we show that a digraph covers a complete digraph if and only if the vertex set of this digraph can be partitioned into perfect directed codes. Equivalent conditions for subsets in Cayley digraphs to be perfect directed codes are given. Especially, equivalent conditions for normal subsets, normal subgroups, and subgroups to be perfect directed codes in Cayley digraphs are given. Moreover, we show that every subgroup of a finite group is a perfect directed code for a transversal Cayley digraph.

References

[1]	S. D. Andres, W. Hochstättler, Perfect Digraphs, J. Graph Theory, 79 (2014), 21–29. https://doi.org/10.1002/jgt.21811 doi: 10.1002/jgt.21811
[2]	T. Araki, On the $k$-tuple domination in de Bruijn and Kautz digraphs, Inform. Process. Lett., 104 (2007), 86–90. https://doi.org/10.1016/j.ipl.2007.05.010 doi: 10.1016/j.ipl.2007.05.010
[3]	T. Araki, The $k$-tuple twin domination in de Bruijn and Kautz digraphs, Discrete Math., 308 (2008), 6406–6413. https://doi.org/10.1016/j.disc.2007.12.020 doi: 10.1016/j.disc.2007.12.020
[4]	S. Arumugam, K. Ebadi, L. Sathikala, Twin domination and twin irredundance in digraphs, Appl. Anal. Discrete Math., 7 (2013), 275–284. https://doi.org/10.2298/AADM130429007A doi: 10.2298/AADM130429007A
[5]	M. Atapour, A. Bodaghli, S. M. Sheikholeslami, Twin signed total domination numbers in directed graphs, Ars Combin., 138 (2018), 119–131.
[6]	B. Bollobás, Modern graph theory, Springer New York, 1998.
[7]	R. Q. Feng, H. Huang, S. M. Zhou, Perfect codes in circulant graphs, Discrete Math., 340 (2017), 1522–1527. https://doi.org/10.1016/j.disc.2017.02.007 doi: 10.1016/j.disc.2017.02.007
[8]	J. Bang-Jensen, G. Gutin, Digraphs: theory, algorithms and applications (Second Edition), Springer Science Business Media, 2008.
[9]	G. Chartrand, P. Dankelmann, M. Schultz, H. C. Swart, Twin domination in digraphs, Ars Combin., 67 (2003), 105–114.
[10]	J. Ghoshal, R. Laskar, D. Pillone, Topics on domination in directed graphs, Domination in Graphs Advanced Topics, (2017), 401–438.
[11]	P. Hall, On representatives of subsets, J. London Math. Soc., 10 (1935), 26–30. https://doi.org/10.1112/jlms/s1-10.37.26 doi: 10.1112/jlms/s1-10.37.26
[12]	J. Huang, J. M. Xu, The total domination and total bondage numbers of extended de Bruijn and Kautz digraphs, Comput. Math. Appl., 53 (2007), 1206–1213. https://doi.org/10.1016/j.camwa.2006.05.020 doi: 10.1016/j.camwa.2006.05.020
[13]	J. Lee, Independent perfect domination sets in Cayley graphs, J. Graph Theory, 37 (2001), 213–219. https://doi.org/10.1002/jgt.1016 doi: 10.1002/jgt.1016
[14]	Y. Kikuchi, Y. Shibata, On the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs, Inform. Process. Lett., 86 (2003), 79–85. https://doi.org/10.1016/S0020-0190(02)00479-9 doi: 10.1016/S0020-0190(02)00479-9
[15]	H. E. Rose, A course on finite groups, Springer London, 2009
[16]	E. F. Shan, Y. X. Dong, Y. K. Cheng, The twin domination number in generalized de Bruijn digraphs, Inform. Process. Lett., 109 (2009), 856–860. https://doi.org/10.1016/j.ipl.2009.04.010 doi: 10.1016/j.ipl.2009.04.010
[17]	Y. L. Wang, Efficient twin domination in generalized De Bruijn digraphs, Discrete Math., 338 (2015), 36–40. https://doi.org/10.1016/j.disc.2014.10.014 doi: 10.1016/j.disc.2014.10.014
[18]	M. Ždímalová, M. Olejár, Large Cayley digraphs of given degree and diameter from sharply $t$-transitive groups Australasian J. Combin., 47 (2010), 211–216.
[19]	M. Ždímalová, L. Staneková, Which Faber-Moore-Chen digraphs are cayley digraphs? Discrete Math., 310 (2010), 2238–2240. https://doi.org/10.1016/j.disc.2010.04.020 doi: 10.1016/j.disc.2010.04.020

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)