1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Domination Parameters of the Unitary Cayley Graph of 𝕑/n𝕑

Published Online: 29 Sep 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

The unitary Cayley graph of 𝕑/n𝕑, denoted Xn, is the graph with vertex set {0, . . ., n − 1} where vertices a and b are adjacent if and only if gcd(ab, n) = 1. We answer a question of Defant and Iyer by constructing a family of infinitely many integers n such that γt(Xn) ≤ 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

MSC 2010

[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.Search in Google Scholar

[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. doi:10.37236/20610.37236/206Search in Google Scholar

[3] R. Akhtar, A.B. Evans and D. Pritikin, Representation numbers of complete multi-partite graphs, Discrete Math. 312 (2012) 1158–1165. doi:10.1016/j.disc.2011.12.00310.1016/j.disc.2011.12.003Search in Google Scholar

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

[5] N. Biggs, Algebraic Graph Theory, Second Edition (Cambridge University Press, Cambridge, 1993). doi:10.1017/CBO978051160870410.1017/CBO9780511608704Search in Google Scholar

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

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

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

[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. doi:10.1016/0166-218X(94)90011-610.1016/0166-218X(94)90011-6Search in Google Scholar

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

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

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

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

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

[15] J.A. Gallian, Graph labeling, A dynamic survey, Electron. J. Combin. (2018) #DS6. doi:10.37236/2710.37236/27Search in Google Scholar

[16] E.N. Gilbert, A comparison of signalling alphabets, The Bell System Technical Journal 31 (1952) 504–522. doi:10.1002/j.1538-7305.1952.tb01393.x10.1002/j.1538-7305.1952.tb01393.xSearch in Google Scholar

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

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

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

[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.Search in Google Scholar

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

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

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

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

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

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo