1
$\begingroup$

Do you know of any pretty well known graph parameters which are equal for all small graphs (for $|G|$ small)? That is, there exist two parameters $a(G)$ and $b(G)$ such that $a(G) = b(G)$ for all graphs with $|G|$ at most $k$, where I will require $k$ to be at least 4 to make things somewhat interesting.

I added "pretty well known" to eliminate defining a new graph parameter trivially to make it work, e.g., let $a(G) = \chi(G)$ for all graphs with $|G| \leq 1000$ and let $a(G) = \pi$ for all graphs with $|G| > 1000$.

The more well known the parameters, and the larger the value of $k$, the better the example!

2 Answers 2

2

$\alpha(G) = \chi(\bar{G})$ for all graphs with $|G| \leq 4$. The first counterexample is the $5$-cycle, and this is the unique counterexample of order $5$. For all orders greater than 5, there are counterexamples. Or, taking the complement of the graphs in both sides gives $\omega(G) = \chi(G)$. These two examples are thus equivalent.

Here, $\alpha(G)$ is the independence number, $\omega(G)$ is the clique number, and $\chi(G)$ is the chromatic number. This, has to do with perfect graphs.

0

The crossing number $\nu(G)$ is the minimum number of crossings in a drawing of $G$ in the plane; the rectilinear crossing number $\bar\nu(G)$ is the minimum number of crossings in a straight line drawing of $G$ in the plane.

I don't know much about this subject, and in particular I don't know the value of $k$. According to the page I linked to, $\nu(K_8)=18$ and $\bar\nu(K_8)=19$. The two parameters are equal for all graphs of order $5$ or less, since $\nu(K_5)=\bar\nu(K_5)=1$ and $\nu(K_5-e)=\bar\nu(K_5-e)=0$. According to a result of Bienstock and Dean mentioned on that page, $\nu(G)=\bar\nu(G)$ whenever $\nu(G)\le3$; so in particular $\nu(G)=\bar\nu(G)$ for all graphs $G$ of order at most $6$, seeing as $\nu(K_6)=3$. I don't know about order $7$.