2
$\begingroup$

I am looking for a list of small graphs (say on less than 10 vertices) for which the parameter $p(G) = \frac{\alpha(G) \omega(G)}{n}$ is small. Here $\alpha(G)$ and $\omega(G)$ is the size of the largest independent set and largest clique in $G$ respectively. Currently, the best example I have is the $5$ cycle, for which $p(G) = 0.8$. There exist examples as mentioned here for lower $p(G)$ values, but all the constructions seem complex and are for large graphs (for example in Paley graphs, $p(G)<0.8$ only after the $13$ vertices$).

Is there a place where someone has exhaustively checked all small graphs?

Improve this question
$\endgroup$
4
  • $\begingroup$ What do you mean by small? There are only about 12 million 10 vertex graphs, it shouldn't be hard to write a program to check them all. You could probably go quite a lot higher with more specific program. This also seems related to lower bounds for Ramsey numbers, they might give good examples. You can see some here $\endgroup$
    – Daniel Weber
    Commented Feb 15 at 8:17
  • $\begingroup$ I am interested in those with $p(G)<0.8$. Thanks, the link seems helpful. $\endgroup$
    – Agile_Eagle
    Commented Feb 15 at 8:36
  • $\begingroup$ If you look at a random graph $G$ on $n$ vertices, the asymptotically almost surely you should have no clique nor indpendent set of size $(1/2)\log_2(n)$. Thus for large $n$, 99% of graphs satisfy $\rho(G)= O(\log(n)^2 /n)$. $\endgroup$
    – Zach Hunter
    Commented Feb 18 at 15:19
  • $\begingroup$ so, if you also care about the large $n$ behavior, this should be useful. $\endgroup$
    – Zach Hunter
    Commented Feb 18 at 15:20

1 Answer 1

Reset to default
6
$\begingroup$

See http://users.cecs.anu.edu.au/~bdm/data/ramsey.html , which contains maximum Ramsey graphs. Ramsey graphs are closely linked to your problem, because the largest graph with $\alpha(G) = a, \omega(G) = b$ will be a maximum $(a+1, b+1)$ Ramsey graph. Looking at the graphs there, the smallest $\rho$ per size is:

  • There's a (3,4,8) graph, giving $\rho(G) = \frac34$.
  • There's a (3,5,13) graph, giving $\rho(G) = \frac8{13}$.
  • There's a (4,4,17) graph, giving $\rho(G) = \frac9{17}$.
  • There's a (4,5,24) graph, giving $\rho(G) = \frac12$.
  • There's a (3,8,27) graph, giving $\rho(G) = \frac{14}{27}$.
  • There's a (4,6,35) graph, giving $\rho(G) = \frac37$.
  • There's a (5,5,42) graph, giving $\rho(G) = \frac8{21}$.

Note that you can drop nodes from graphs to produce values for $n$'s between these sizes.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .