Achromatic numbers for circulant graphs and digraphs

Abstract

In this paper, we determine the achromatic and diachromatic numbers of some circulant graphs and digraphs each one with two lengths and give bounds for other circulant graphs and digraphs with two lengths. In partic ular, for the achromatic number we state that α(C16q 2+20q+7(1, 2)) = 8q+ 5, and for the diachromatic number we state that dac( −→C 32q 2+24q+5(1, 2)) = 8q + 3. In general, we give the lower bounds α(C4q 2+aq+1(1, a)) ≥ 4q + 1 and dac( −→C 8q 2+2(a+4)q+a+3(1, a)) ≥ 4q + 3 when a is a non quadratic residue of Z4q+1 for graphs and Z4q+3 for digraphs, and the equality is attained, in both cases, for a = 3. Finally, we determine the achromatic index for circulant graphs of q 2 + q + 1 vertices when the projective cyclic plane of odd order q exists.