Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1709260 | Applied Mathematics Letters | 2009 | 6 Pages |
The concept of gcd-graphs is introduced by Klotz and Sander; they arise as a generalization of unitary Cayley graphs. The gcd-graph Xn(d1,…,dk)Xn(d1,…,dk) has vertices 0,1,…,n−10,1,…,n−1, and two vertices xx and yy are adjacent iff gcd(x−y,n)∈D={d1,d2,…,dk}gcd(x−y,n)∈D={d1,d2,…,dk}. These graphs are exactly the same as circulant graphs with integral eigenvalues characterized by So. In this work we deal with the clique number of integral circulant graphs and investigate the conjecture proposed in [W. Klotz, T. Sander, Some properties of unitary Cayley graphs, The Electronic Journal of Combinatorics 14 (2007) #R45] that the clique number divides the number of vertices in the graph Xn(D)Xn(D). We completely solve the problem of finding the clique number for integral circulant graphs with exactly one and two divisors. For k⩾3k⩾3, we construct a family of counterexamples and disprove the conjecture in this case.