Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 NP-complete? (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.

share|improve this question
    
There is lots of information (though not an answer to your exact question) at en.wikipedia.org/wiki/Clique_problem. –  Hugh Thomas Jun 24 at 4:06

1 Answer 1

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 NP-complete when restricted to 3-regular planar graphs.

Reference:

COMPUTERS AND Intractability, A Guide to the Theory of NP-Completeness

Michael R. Garey / David S. Johnson

page 194-195

share|improve this answer
1  
This answers the question for cliques of specified size, but it doesn't answer it for cliques of size n/2. 3-regular graphs have an independent set of size $n/2$ iff they are bipartite. –  Brendan McKay Jun 25 at 19:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.