Geodesic
Domination parameters of the unitary Cayley graph of $\mathbb{Z} // n\mathbb{Z}$
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 95-114 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

The unitary Cayley graph of ℤ // nℤ, denoted X_n, is the graph with vertex set {0, . . . ,n-1} where vertices a and b are adjacent if and only if (a-b,n) = 1. We answer a question of Defant and Iyer by constructing a family of infinitely many integers n such that γ_t(X_n) ≤ g(n) - 2, where γ_t denotes the total domination number and g denotes the Jacobsthal function. We determine the irredundance number, domination number, and lower independence number of certain direct products of complete graphs and give bounds for these parameters for any direct product of complete graphs. We provide upper bounds on the size of irredundant sets in direct products of balanced, complete multipartite graphs which are asymptotically correct for the unitary Cayley graphs of integers with a bounded smallest prime factor.
Keywords: unitary Cayley graph, domination chain, direct product, complete balanced multipartite graph 
@article{DMGT_2023_43_1_a5,
     author = {Burcroff, Amanda},
     title = {Domination parameters of the unitary {Cayley} graph of $\mathbb{Z} // n\mathbb{Z}$},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {95--114},
     year = {2023},
     volume = {43},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a5/}
}
TY  - JOUR
AU  - Burcroff, Amanda
TI  - Domination parameters of the unitary Cayley graph of $\mathbb{Z} // n\mathbb{Z}$
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 95
EP  - 114
VL  - 43
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a5/
LA  - en
ID  - DMGT_2023_43_1_a5
ER  - 
%0 Journal Article
%A Burcroff, Amanda
%T Domination parameters of the unitary Cayley graph of $\mathbb{Z} // n\mathbb{Z}$
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 95-114
%V 43
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a5/
%G en
%F DMGT_2023_43_1_a5
Burcroff, Amanda. Domination parameters of the unitary Cayley graph of $\mathbb{Z} // n\mathbb{Z}$. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 95-114. http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a5/

[1] R.B. Allan and R. Laskar, On domination and some related topics in graph theory, in: Proceedings of the Ninth Southeast Conference on Combinatorics, Graph Theory, and Computing, Util. Math. (1978) 43–56.

[2] R. Akhtar, M. Boggess, T. Jackson-Henderson, I. Jiménez, R. Karpman, A. Kinzel and D. Pritikin, On the unitary Cayley graph of a finite ring, Electron. J. Combin. 16 (2009) #R117. https://doi.org/10.37236/206

[3] R. Akhtar, A.B. Evans and D. Pritikin, Representation numbers of complete multipartite graphs, Discrete Math. 312 (2012) 1158–1165. https://doi.org/10.1016/j.disc.2011.12.003

[4] N. Alon and C. Defant, Isoperimetry, stability, and irredundance in direct products, Discrete Math. 343 (2020) 111902. https://doi.org/10.1016/j.disc.2020.111902

[5] N. Biggs, Algebraic Graph Theory, Second Edition (Cambridge University Press, Cambridge, 1993). https://doi.org/10.1017/CBO9780511608704

[6] B. Bollobás and E.J. Cockayne, Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory 3 (1979) 241–249. https://doi.org/10.1002/jgt.3190030306

[7] B. Brešar, S. Klavžar and D.F. Rall, Dominating direct products of graphs, Discrete Math. 307 (2007) 1636–1642. https://doi.org/10.1016/j.disc.2006.09.013

[8] K. Budadoddi and A. Mallikarjuna Reddy, Cycle dominating sets of Euler totient Cayley graphs, Math. Sci. Int. Res. J. 3 (2014) 727–730.

[9] G.A. Cheston and G.H. Fricke, Classes of graphs for which the upper fractional domination equals independence, upper domination, and upper irredundance, Discrete Appl. Math. 55 (1994) 241–258. https://doi.org/10.1016/0166-218X(94)90011-6

[10] C. Defant, Unitary Cayley graphs of Dedekind domain quotients, AKCE Int. J. Graphs Comb. 13 (2016) 65–75. https://doi.org/10.1016/j.akcej.2016.03.001

[11] C. Defant and S. Iyer, Domination and upper domination of direct product graphs, Discrete Math. 341 (2018) 2742–2752. https://doi.org/10.1016/j.disc.2018.06.031

[12] P. Erdős and A.B. Evans, Representations of graphs and orthogonal Latin square graphs, J. Graph Theory 13 (1989) 593–595. https://doi.org/10.1002/jgt.3190130509

[13] A.B. Evans, Representations of disjoint unions of complete graphs, Discrete Math. 307 (2007) 1191–1198. https://doi.org/10.1016/j.disc.2006.07.029

[14] A.B. Evans, G. Isaak and D.A. Narayan, Representations of graphs modulo n, Discrete Math. 223 (2000) 109–123. https://doi.org/10.1016/S0012-365X(00)00062-5

[15] J.A. Gallian, Graph labeling, A dynamic survey, Electron. J. Combin. (2018) #DS6. https://doi.org/10.37236/27

[16] E.N. Gilbert, A comparison of signalling alphabets, The Bell System Technical Journal 31 (1952) 504–522. https://doi.org/10.1002/j.1538-7305.1952.tb01393.x

[17] C. Godsil and G. Royle, Algebraic Graph Theory, in: Grad. Texts in Math. 207 (Springer-Verlag, New York, 2001). https://doi.org/10.1007/978-1-4613-0163-9

[18] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc, New York, 1998). https://doi.org/10.1201/9781482246582

[19] W. Klotz and T. Sander, Some properties of unitary Cayley graphs, Electron. J. Combin. 14 (2007) #R45. https://doi.org/10.37236/963

[20] S.U. Maheswari and B. Maheswari, Independent domination number of Euler totient Cayley graphs and arithmetic graphs, Int. J. Adv. Res. Eng. Technol. 7(3) (2016) 56–65.

[21] M. Manjuri and B. Maheswari, Strong dominating sets of some arithmetic graphs, Int. J. Comput. Appl. 83(3) (2013) 36–40. https://doi.org/10.5120/14431-2577

[22] G. Mekiš, Lower bounds for the domination number and the total domination number of direct product graphs, Discrete Math. 310 (2010) 3310–3317. https://doi.org/10.1016/j.disc.2010.07.015

[23] M. Valencia-Pabon, Idiomatic partitions of direct products of complete graphs, Discrete Math. 310 (2010) 1118–1122. https://doi.org/10.1016/j.disc.2009.10.012

[24] R.R. Varshamov, Estimate of the number of signals in error correcting codes, Dokl. Akad. Nauk 117 (1957) 739–741.

[25] H.J. Veldman, Existence of dominating cycles and paths, Discrete Math. 43 (1983) 281–296. https://doi.org/10.1016/0012-365X(83)90165-6

[26] H. Vemuri, Domination in direct products of complete graphs, Discrete Appl. Math. 285 (2020) 473–482. https://doi.org/10.1016/j.dam.2020.06.015