On the clique number of integral circulant graphs

Details On the clique number of integral circulant graphs On the clique number of integral circulant graphs

2011-04-06

arxiv.org/abs/1104.1107v1

Appl. Math. Lett. 22 (2009) 1406-1411

Mathematics

Combinatorics

6 pages, 1 figure

Scientific paper

The concept of gcd-graphs is introduced by Klotz and Sander, which arises as a generalization of unitary Cayley graphs. The gcd-graph $X_n (d_1,...,d_k)$ has vertices $0,1,...,n-1$, and two vertices $x$ and $y$ are adjacent iff $\gcd(x-y,n)\in D = \{d_1,d_2,...,d_k\}$. These graphs are exactly the same as circulant graphs with integral eigenvalues characterized by So. In this paper we deal with the clique number of integral circulant graphs and investigate the conjecture proposed in \cite{klotz07} that clique number divides the number of vertices in the graph $X_n (D)$. We completely solve the problem of finding clique number for integral circulant graphs with exactly one and two divisors. For $k \geqslant 3$, we construct a family of counterexamples and disprove the conjecture in this case.

Affiliated with

Also associated with

No associations

Rating

On the clique number of integral circulant graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the clique number of integral circulant graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the clique number of integral circulant graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-418085