5

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.

graph

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

flag
2 
 Joel, I did contact David Eppstein before I posted here actually. He said that the main property that he knew it for was that it did not have a perfect matching, as opposed to bipartite or 2-connected cubic graphs. – David Roberson Oct 18 2011 at 6:37
2 
 Anton: all 3-regular graphs have an even number of vertices. – David Eppstein Oct 18 2011 at 6:45
6 
 Why would having an even number of vertices be an embarrassment to 3-regular graphs? – Mariano Suárez-Alvarez Oct 18 2011 at 6:56
4 
 In particular this graph is the smallest simple cubic graph with no perfect matching. – Andrew D. King Oct 18 2011 at 13:40
3 
 It deserves a better name than that. – David Eppstein Oct 18 2011 at 15:01
show 6 more comments

1 Answer

2

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.

link|flag

Your Answer

Get an OpenID
or

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