I am looking for NP complete results for cliques in regular graphs. For example is the general problem of determining if a regular graph on n vertices has an n/2 clique NPcomplete? (obviously the question is interesting only if the degree is at least n/2). You could also ask the same question for say regular graphs of degree 3n/4.
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $G = (V,E)$ be a graph and $c ≤ V $ a positive integer. The independent sets of $G$ are precisely the cliques of the complementary graph $\overline{G}$. INDEPENDENT SET INSTANCE: Graph $G=(V,E)$, positive integer $c$. QUESTION: Does $G$ contain an independent set of size $c$ or more, The independent set problem remains NPcomplete when restricted to 3regular planar graphs. Reference: COMPUTERS AND Intractability, A Guide to the Theory of NPCompleteness Michael R. Garey / David S. Johnson page 194195 

