Let $G$ be simple graph of order $N$, and let $\bar{d}$ be its average degree.

  1. Find the maximum value of $\omega(G)$ (the clique number of $G$) as a function of $N$ and $\bar{d}$.

  2. Find the minimum value of $\omega(G)$ as a function of $n$ and $\bar{d}$.

  3. What are the minimum and maximum values of $\omega(G)$ when $G$ is $d$-regular?

  • 3
    $\begingroup$ This seems like homework. What have you tried? Where are you stuck? $\endgroup$ – Pål GD Feb 18 '19 at 8:53
  • $\begingroup$ I feel like the first part should be a quadratic function(probably). Something like k(k-1)/2 where k is size of maximum clique. I'm not sure how to approach this question when the graph is d-regular though! $\endgroup$ – Ritwik Feb 18 '19 at 10:13
  • $\begingroup$ When the graph is $d$-regular, certainly $\omega(G) \leq d+1$, and this is achievable (for example, a clique $K_{d+1}$). Conversely, if $d \leq n$, then you can take the graph on $x_1,\ldots,x_n,y_1,\ldots,y_n$ (so $N = 2n$) containing the edges $(x_i,y_{i+j \bmod n})$ for $1 \leq j \leq d$, which is $d$-regular but triangle-free. $\endgroup$ – Yuval Filmus Feb 18 '19 at 11:15
  • $\begingroup$ Please edit the question to credit the original source for all copied or quoted material. Also, you might find this page helpful in improving your question. Finally, please ask only one question per post. If you have multiple questions, you can post each one separately. $\endgroup$ – D.W. Feb 18 '19 at 20:33

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.