8
$\begingroup$

A student wanted a challenging Graph Theory programming project and I had him try to determine the maximum value of the Cheeger number (isoperimetric number) among all 3-regular graphs of order $n$, for small values of $n$. The program we devised seems reasonably efficient, and I wonder if there is any similar data out there that we can use for comparison purposes?

(One amusing side note is that the Pappus graph seems to have an unusually large Cheeger number for it's order, larger than any order $16$ graph or any other order $18$ graph.)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

I did this calculation a few years ago (according to the timestamps on my programs).

Here is the summary of my results for $n=18$ (total of $41301$ graphs), with each line being the number of graphs followed by a particular Cheeger value.

190 0.111111
450 0.142857
795 0.200000
2002 0.250000
6280 0.333333
5542 0.428571
14909 0.500000
9793 0.555556
6 0.600000
69 0.666667
973 0.714286
291 0.750000
1 0.777778

I also conclude that the unique $18$-vertex graph with maximum Cheeger constant is the Pappus graph.

I can't actually remember why I calculated these numbers, but obviously whatever it was for did not lead to anything, and I haven't seen anything in the literature about Cheeger numbers of cubic graphs in particular. There are a few papers about isoperimetric numbers of families of graphs, but I am sure you can Google them as well as I can.

ADDED: There are 11 cubic graphs on 20 vertices with the same extremal Cheeger constant as the Pappus graph. I expect that they are all minor perturbations of the Pappus graph, but do not know for sure.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Nozaki studied a similar problem (among all k-regular graphs of given order v, find the one(s) with the smallest second eigenvalue of the adjacency matrix): arxiv.org/abs/1407.4562 Nozaki obtained a linear programming bound for graphs. With Nozaki, Koolen and Vermette, I studied a related, but different problem (given $k$ and $\lambda$, find the largest order of a $k$-regular graph with second eigenvalue at most $\lambda$); we used Nozaki's LP bound and interlacing. The Pappus graph appeared as extremal (largest cubic graph with $\lambda_2\leq \sqrt{3}$): arxiv.org/abs/1503.06286 $\endgroup$
    – Sebi Cioaba
    Commented Jun 16, 2015 at 12:19
  • 3
    $\begingroup$ I have one happy student now. Another aspect of Pappus being special is that for n=16 the max is smaller than for n=18, and for n=20 it stays the same (if I can now trust his program); whereas in general the max seems to decrease (or stay the same) as n increases. Of course these small values don't mean much. $\endgroup$
    – user71114
    Commented Jun 16, 2015 at 14:20

You must log in to answer this question.