# Clique number of a $k$th power of a graph in terms of maximum degree?

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?

• 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? Apr 4, 2013 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$. Apr 4, 2013 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.) Apr 5, 2013 at 1:36