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
    Commented 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
    Commented Oct 18, 2011 at 6:56
  • 7
    $\begingroup$ In particular this graph is the smallest simple cubic graph with no perfect matching. $\endgroup$
    – Andrew D. King
    Commented Oct 18, 2011 at 13:40
  • 5
    $\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
    Commented Oct 18, 2011 at 14:56
  • 4
    $\begingroup$ It deserves a better name than that. $\endgroup$
    – David Eppstein
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .