A COMBINATORIAL METHOD FOR CALCULATING CLIQUE NUMBER OF SPECIAL GRAPHS

The graph G(d) q;n is a graph with vertex set Zq £ ¢ ¢ ¢ £ Zq, (n- fold), in which two vertices are joined by an edge if their distance is at most d. Consider verex x of G(d) q;n also as a word of length n over the alphabet Zq. All words of weight up to t = b d 2 c induced a clique of G(d) q;n and if d is odd these words and all words of weight t + 1 with a non-zero entry in the first position construct a clique. Therefore the number of these words is a bound for the clique number. In this paper, explicit formulas for the clique number !(G(d) q;n) have been presented.