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?

  • $\begingroup$ 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? $\endgroup$ Apr 4 '13 at 8:59
  • 1
    $\begingroup$ 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$. $\endgroup$ Apr 4 '13 at 20:01
  • $\begingroup$ 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.) $\endgroup$ Apr 5 '13 at 1:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.