MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $G$ be a graph of maximum degree $d$. Are there any known/easy bounds on the clique number of $G^k$, in terms of $d$ and $k$? I would like something at least epsilon better than the bound on the degree of $G^k$ (something like half of this bound would be very nice, and not surprising), and am particularly interested in the case $d=4$ and $k=4$.

EDIT: Apparently this is well-studied, and called the degree-diameter problem. So here is a twist: what if some vertex is in at least two triangles?

share|cite|improve this question
The degree-diameter problem is the problem of maximising the number of vertices in a graph of fixed degree and diameter. I can't see the connection to either cliques or powers of graphs? – Gordon Royle Apr 4 '13 at 8:59
Gordon, a maximum $m(d,k)$ on the clique size of $G^k$ is the same as the maximum number of vertices in a graph of diameter at most $k$, as the vertices of a clique in $G^k$ induce a subgraph of diameter at most $k$ in $G$. – Flo Pfender Apr 4 '13 at 20:01
Yes; they are related but not equivalent problems, because you could have vertices that are not in your clique, but help to connect vertices. I think the numbers should be close but not equal. (Aside from this question, I have found a better way to solve the problem I was working on.) – Andrew D. King Apr 5 '13 at 1:36

Your Answer


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

Browse other questions tagged or ask your own question.