3
$\begingroup$

I'm trying to find the smallest graph that is regular but not vertex-transitive, where by smallest I mean "least number of vertices", and if two graphs have the same number of vertices, then the smaller is the one with the lower number of edges.

I currently have that the smallest such graph is the disjoint union of the three-cycle and the four-cycle.

Are there any smaller graphs?

$\endgroup$
3
$\begingroup$

Note that a graph is vertex transitive if and only if its complement is, and a regular graph on at most six vertices is the complement of a regular graph with valency at most two. It is easy to write down all graphs with valency at most two on at most six vertices.

$\endgroup$
  • $\begingroup$ Is that easy? There are many graphs on at most six vertices. Even to eliminate all the ones with valency $> 2$ would still leave me checking on the order of $2^{15}$ graphs. Is there a particular technique you have in mind? $\endgroup$ – Newb Apr 21 '14 at 12:00
  • $\begingroup$ You only want regular graphs on at most six vertices with max valency two. There are not very many. If these are all vertex transitive, then all regular graphs with at most six vertices are vertex transitive. $\endgroup$ – Chris Godsil Apr 21 '14 at 12:07
  • $\begingroup$ Okay, I sketched it out. The regular graphs on $n$ vertices with valency $2$ are all just cycles, which are vertex-transitive. Is that correct? This leads me to believe that I've found the minimal example (seeing as a regular graph on 7 vertices with fewer than 7 edges is not possible). $\endgroup$ – Newb Apr 21 '14 at 12:12
  • $\begingroup$ @Newb Yes. A regular graph with valency $0$ is trivially transitive. Regular with valency $1$ is always vertex transitive (it's just a bunch of isolated edges). Regular with valency $2$ means we have disjoint cycles; as each must have length $\ge3$, to even have more than one cycle (which is always transitive) we need $n\ge 6$; with $n=6$ we could have two $3$-cycles, still transitive; with $n=7$, we have your example. $\endgroup$ – Hagen von Eitzen Apr 21 '14 at 12:27
  • $\begingroup$ @HagenvonEitzen As I thought. Thanks for making it clear! $\endgroup$ – Newb Apr 21 '14 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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