Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
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 '11 at 6:37
2  
Anton: all 3-regular graphs have an even number of vertices. –  David Eppstein Oct 18 '11 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 '11 at 6:56
4  
In particular this graph is the smallest simple cubic graph with no perfect matching. –  Andrew D. King Oct 18 '11 at 13:40
3  
It deserves a better name than that. –  David Eppstein Oct 18 '11 at 15:01
show 6 more comments

1 Answer 1

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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