Extremal regular graphs for the achromatic number

The problem of constructing (m, n) cages suggests the following class of problems. For a graph parameter θ, determine the minimum or maximum value of p for which there exists a k-regular graph on p points having a given value of θ. The minimization problem is solved here when θ is the achromatic number, denoted by ψ. This result follows from the following main theorem. Let M(p, k) be the maximum value of ψ(G) over all k-regular graphs G with p points, let {x} be the least integer of size at least x, and let be given by ω(k) = {i(ik+1)+1:1i<∞}. Define the function ƒ(p, k) by

Full-size image

. Then for fixed k2 we have M(p, K=ƒ(p, k) if pω(k) and M(p, k)=ƒ(p,k-1 if pε ω(k) for all p sufficiently large with respect to k.