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.

Keywords:

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:

[1]	Jianjun Huang, Xuhong Huang, Ronghao Kang, Zhihong Chen, Junhan Peng . Improved insulator location and defect detection method based on GhostNet and YOLOv5s networks. Electronic Research Archive, 2024, 32(9): 5249-5267. doi: 10.3934/era.2024242
[2]	Ye Yu, Zhiyuan Liu . A data-driven on-site injury severity assessment model for car-to-electric-bicycle collisions based on positional relationship and random forest. Electronic Research Archive, 2023, 31(6): 3417-3434. doi: 10.3934/era.2023173
[3]	Min Li, Ke Chen, Yunqing Bai, Jihong Pei . Skeleton action recognition via graph convolutional network with self-attention module. Electronic Research Archive, 2024, 32(4): 2848-2864. doi: 10.3934/era.2024129
[4]	Linan Fang, Ting Wu, Yongxing Qi, Yanzhao Shen, Peng Zhang, Mingmin Lin, Xinfeng Dong . Improved collision detection of MD5 with additional sufficient conditions. Electronic Research Archive, 2022, 30(6): 2018-2032. doi: 10.3934/era.2022102
[5]	Hui Xu, Jun Kong, Mengyao Liang, Hui Sun, Miao Qi . Video behavior recognition based on actional-structural graph convolution and temporal extension module. Electronic Research Archive, 2022, 30(11): 4157-4177. doi: 10.3934/era.2022210
[6]	Lei Pan, Chongyao Yan, Yuan Zheng, Qiang Fu, Yangjie Zhang, Zhiwei Lu, Zhiqing Zhao, Jun Tian . Fatigue detection method for UAV remote pilot based on multi feature fusion. Electronic Research Archive, 2023, 31(1): 442-466. doi: 10.3934/era.2023022
[7]	Chang Yu, Qian Ma, Jing Li, Qiuyang Zhang, Jin Yao, Biao Yan, Zhenhua Wang . FF-ResNet-DR model: a deep learning model for diabetic retinopathy grading by frequency domain attention. Electronic Research Archive, 2025, 33(2): 725-743. doi: 10.3934/era.2025033
[8]	Miao Luo, Yousong Chen, Dawei Gao, Lijun Wang . Inversion study of vehicle frontal collision and front bumper collision. Electronic Research Archive, 2023, 31(2): 776-792. doi: 10.3934/era.2023039
[9]	Tong Li, Lanfang Lei, Zhong Wang, Peibei Shi, Zhize Wu . An efficient improved YOLOv10 algorithm for detecting electric bikes in elevators. Electronic Research Archive, 2025, 33(6): 3673-3698. doi: 10.3934/era.2025163
[10]	Jinjiang Liu, Yuqin Li, Wentao Li, Zhenshuang Li, Yihua Lan . Multiscale lung nodule segmentation based on 3D coordinate attention and edge enhancement. Electronic Research Archive, 2024, 32(5): 3016-3037. doi: 10.3934/era.2024138

Abstract

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

This article has been cited by:

1.	Gregory Roth, Paul L. Salceanu, Sebastian J. Schreiber, Robust Permanence for Ecological Maps, 2017, 49, 0036-1410, 3527, 10.1137/16M1066440
2.	Jude D. Kong, Paul Salceanu, Hao Wang, A stoichiometric organic matter decomposition model in a chemostat culture, 2018, 76, 0303-6812, 609, 10.1007/s00285-017-1152-3
3.	Muhammad Dur-e-Ahmad, Mudassar Imran, Adnan Khan, Analysis of a Mathematical Model of Emerging Infectious Disease Leading to Amphibian Decline, 2014, 2014, 1085-3375, 1, 10.1155/2014/145398
4.	Paul L. Salceanu, Robust uniform persistence in discrete and continuous nonautonomous systems, 2013, 398, 0022247X, 487, 10.1016/j.jmaa.2012.09.005
5.	Azmy S. Ackleh, Robert J. Sacker, Paul Salceanu, On a discrete selection–mutation model, 2014, 20, 1023-6198, 1383, 10.1080/10236198.2014.933819
6.	Mudassar Imran, Muhammad Usman, Muhammad Dur-e-Ahmad, Adnan Khan, Transmission Dynamics of Zika Fever: A SEIR Based Model, 2017, 0971-3514, 10.1007/s12591-017-0374-6
7.	Azmy S. Ackleh, John Cleveland, Horst R. Thieme, Population dynamics under selection and mutation: Long-time behavior for differential equations in measure spaces, 2016, 261, 00220396, 1472, 10.1016/j.jde.2016.04.008
8.	AZMY S. ACKLEH, J. M. CUSHING, PAUL L. SALCEANU, ON THE DYNAMICS OF EVOLUTIONARY COMPETITION MODELS, 2015, 28, 08908575, 380, 10.1111/nrm.12074
9.	Mudassar Imran, Muhammad Usman, Tufail Malik, Ali R. Ansari, Mathematical analysis of the role of hospitalization/isolation in controlling the spread of Zika fever, 2018, 255, 01681702, 95, 10.1016/j.virusres.2018.07.002
10.	Azmy S. Ackleh, Paul L. Salceanu, Competitive exclusion and coexistence in ann-species Ricker model, 2015, 9, 1751-3758, 321, 10.1080/17513758.2015.1020576
11.	Azmy S. Ackleh, Paul Salceanu, Amy Veprauskas, A nullcline approach to global stability in discrete-time predator–prey models, 2021, 27, 1023-6198, 1120, 10.1080/10236198.2021.1963440
12.	Térence Bayen, Henri Cazenave-Lacroutz, Jérôme Coville, Stability of the chemostat system including a linear coupling between species, 2023, 28, 1531-3492, 2104, 10.3934/dcdsb.2022160
13.	Qihua Huang, Paul L. Salceanu, Hao Wang, Dispersal-driven coexistence in a multiple-patch competition model for zebra and quagga mussels, 2022, 28, 1023-6198, 183, 10.1080/10236198.2022.2026342
14.	Hayriye Gulbudak, Paul L. Salceanu, Gail S. K. Wolkowicz, A delay model for persistent viral infections in replicating cells, 2021, 82, 0303-6812, 10.1007/s00285-021-01612-3
15.	J. C. Macdonald, H. Gulbudak, Forward hysteresis and Hopf bifurcation in an Npzd model with application to harmful algal blooms, 2023, 87, 0303-6812, 10.1007/s00285-023-01969-7

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)