How can one construct a densest graph with no k-clique?
Turan's theorem exactly characterizes the densest graphs on n vertices with no k clique. The Turan graphs are the maximal graphs, and they're very easy to construct. Is this what you want?