Is this possible? I have a 4-connected 17-graph and am wondering whether there are another 3 like it that can be put together to make its complement. My current 4-connected example is here
edge-partitioning a strongly connected 17-graph into four 4-connected 17-graphs
-
0Basically my question is motivated by seeing this: http://scienceblogs.com/goodmath/2007/07/graph_decomposition_and_turnin.php . My understanding is that his 'proof' is completely and totally wrong (because it simply doesn't work), but I was wondering if there was another way to do it. – 2011-01-26
1 Answers
Ok, I've been able to decompose K17 into 8 2-regular subgraphs. Here's my solution:
My method is as follows: Starting from any vertex, skip n, and draw an edge to the vertex you ended up at. Repeat the process from the new vertex until you return to your origin. Any complete graph of order 2x+1 can be decomposed into n subgraphs by repeating the above process for values of n from 0 to x-1.
There are many ways to pair the 8 sub-grids so that they become 4 isomorphic 4-regular ones. First choose a type of polygon you'd like to be dominant in your sub-grids. For instance with triangles, you can pair n=1 with n=2 (1/2), then 3/6, 4/8, and 5/7 (since n=7 in a 17-node graph is the same as n=10). Alternatively, you could also pair 2/4, 6/5, 7/3, 8/1. There are also two ways to pair if you're aiming for rectangles and pentagons, and I assume all the way up to octagons, for a total of 12 ways to combine.
-
0Turns out, it's even more interesting than that! When aiming for triangles, there is an alternative combination: 2/4, 6/5, 7/3, 8/1. And there are two ways to combine the subgraphs, whatever(?) type of polygon you're aiming for. I've worked it out for rectangles and pentagons, I'm sure it goes further than that. Trying a 16-gon, it seems to be the mirror of a triangle, so perhaps the limit would be an octagon. – 2011-01-27