Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646519 | AKCE International Journal of Graphs and Combinatorics | 2016 | 11 Pages |
If XX is a commutative ring with unity, then the unitary Cayley graph of XX, denoted GXGX, is defined to be the graph whose vertex set is XX and whose edge set is {{a,b}:a−b∈X×}{{a,b}:a−b∈X×}. When RR is a Dedekind domain and II is an ideal of RR such that R/IR/I is finite and nontrivial, we refer to GR/IGR/I as a generalized totient graph . We study generalized totient graphs as generalizations of the graphs GZ/(n)GZ/(n), which have appeared recently in the literature, sometimes under the name Euler totient Cayley graphs . We begin by generalizing to Dedekind domains the arithmetic functions known as Schemmel totient functions, and we use one of these generalizations to provide a simple formula, for any positive integer mm, for the number of cliques of order mm in a generalized totient graph. We then proceed to determine many properties of generalized totient graphs such as their clique numbers, chromatic numbers, chromatic indices, clique domination numbers, and (in many, but not all cases) girths. We also determine the diameter of each component of a generalized totient graph. We correct one erroneous claim about the clique domination numbers of Euler totient Cayley graphs that has appeared in the literature and provide a counterexample to a second claim about the strong domination numbers of these graphs.