2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\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$
    – Gordon Royle
    Apr 4, 2013 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$
    – Flo Pfender
    Apr 4, 2013 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$
    – Andrew D. King
    Apr 5, 2013 at 1:36

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.