8
$\begingroup$

I recently constructed the graph shown below in the process of investigating some problems regarding line graphs and homomorphisms, and then happened to see it on wikipedia. I was wondering if anyone knew of this graph coming up anywhere else.

enter image description here

If it helps, I was partly inspired by this paper which shows that any graph with maximum degree 3 and circular chromatic index 4 must contain $K_4$ with one edge subdivided as a subgraph. Note that the graph in the link above is three copies of $K_4$ with one edge subdivided plus another vertex which is adjacent to the vertices that are subdividing the edges.

Thanks

Improve this question
$\endgroup$
11
  • 3
    $\begingroup$ Anton: all 3-regular graphs have an even number of vertices. $\endgroup$
    – David Eppstein
    Oct 18, 2011 at 6:45
  • 9
    $\begingroup$ Why would having an even number of vertices be an embarrassment to 3-regular graphs? $\endgroup$
    – Mariano Suárez-Álvarez
    Oct 18, 2011 at 6:56
  • 6
    $\begingroup$ In particular this graph is the smallest simple cubic graph with no perfect matching. $\endgroup$
    – Andrew D. King
    Oct 18, 2011 at 13:40
  • 4
    $\begingroup$ As mentioned in mathworld.wolfram.com/PerfectMatching.html , this graph has been implemented in Mathematica as GraphData["NoPerfectMatchingGraph"]. This appears to confirm that the absence of perfect matchings is its most recognized property. $\endgroup$
    – Sergey Norin
    Oct 18, 2011 at 14:56
  • 3
    $\begingroup$ It deserves a better name than that. $\endgroup$
    – David Eppstein
    Oct 18, 2011 at 15:01

1 Answer 1

Reset to default
3
$\begingroup$

Any connected trivalent graph realises a Schreier coset graph of a subgroup of the modular group. This yields a transitive permutation group of degree 16 x 3 since we expand each node into an oriented triangle. In the original graph, switching the ends of edges & rotating the oriented triangles provides generators of order 2 and order 3. Recall PSL(2,Z) = free product C2 * C3.

Improve this answer
$\endgroup$

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.