Article in volume
Authors:
Title:
Domination parameters of the unitary Cayley graph of $\mathbb{Z}/n\mathbb{Z}$
PDFSource:
Discussiones Mathematicae Graph Theory 43(1) (2023) 95-114
Received: 2019-06-22 , Revised: 2020-07-21 , Accepted: 2020-07-25 , Available online: 2020-09-20 , https://doi.org/10.7151/dmgt.2352
Abstract:
The unitary Cayley graph of $\mathbb{Z}/n\mathbb{Z}$, denoted $X_n$, is the
graph with vertex set $\{0,\dots,n-1\}$ where vertices $a$ and $b$ are adjacent
if and only if $\gcd(a-b,n) = 1$. We answer a question of Defant and Iyer by
constructing a family of infinitely many integers $n$ such that
$\gamma_t(X_n) \leq g(n) - 2$, where $\gamma_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
References:
- 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.
- 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 - 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 - 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 - N. Biggs, Algebraic Graph Theory, Second Edition (Cambridge University Press, Cambridge, 1993).
https://doi.org/10.1017/CBO9780511608704 - 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 - 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 - K. Budadoddi and A. Mallikarjuna Reddy, Cycle dominating sets of Euler totient Cayley graphs, Math. Sci. Int. Res. J. 3 (2014) 727–730.
- 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 - 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 - 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 - 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 - 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 - 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 - J.A. Gallian, Graph labeling, A dynamic survey, Electron. J. Combin. (2018) #DS6.
https://doi.org/10.37236/27 - 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 - 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 - 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 - W. Klotz and T. Sander, Some properties of unitary Cayley graphs, Electron. J. Combin. 14 (2007) #R45.
https://doi.org/10.37236/963 - 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.
- 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 - 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 - 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 - R.R. Varshamov, Estimate of the number of signals in error correcting codes, Dokl. Akad. Nauk 117 (1957) 739–741.
- 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 - 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
Close