Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 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.

share|improve this answer

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.