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
-
0By "like it" do you mean the other graphs should be isomorphic, or simply that they should be 4-connected (on the same nodes) and disjoint? I think you are trying to edge-partition the complete graph $K_17$ with isomorphic copies of the given example. I'd guess it's easier to work computationally with the adjacency matrix. – 2011-01-26
-
0Complement with respect to what? – 2011-01-26
-
1I doubt it's $K_{17}$ he's partitioning. I'm guessing it has something to do with the $17\times 17$ challenge. – 2011-01-26
-
0@mjqxxxx: The phrasing is curious, but if we take "edge-partitioning" in the subject line as the dictum, then arithmetic shows the union of the four "4-connected" graphs (on 17 nodes) must be the complete graph on 17 nodes. – 2011-01-26
-
0@hardmath: You're right... I stand corrected. So now that we know the question, what's the answer? – 2011-01-26
-
0@Hardmath sorry about the ambiguity.. Isomorphic would be ideal, any 4-partitioning that results would still be very interesting. – 2011-01-26
-
0@mjqxxxx It does have to do with 17x17 AND K17 :) – 2011-01-26
-
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.
-
0Clearly you've decomposed $K_{17}$ into eight disjoint 17-cycles, any two of which would combine to give a regular subgraph of degree 4 with minimum cut set of size 4, so in that sense 4-connected. However it is not clear to me whether this can give four isomorphic subgraphs. Are you still interested in the original question whether four copies of the given example will cover $K_{17}$? – 2011-01-26
-
0You're right. 1+2, 3+6, 4+8 are isomorphic but (I think) 5+7 is different. I am certainly still interested in the original question. – 2011-01-26
-
1Maybe 5+7 is also; after all the 7-stride is the same as the 10-stride 17-cycle. These would at least share in the existence of lots of triangles, something your original example has fewer of (if my eyes can be trusted). – 2011-01-26
-
0I think you're right again! for 1/2, for every vertex, following the 1-stride edges gives you vertices linked by a 2-stride edge. Same for 2/4 and 3/6. This is true for 7/5 also, but for each vertex you must follow the 7-stride vertices and you find 5-stride linked vertices. So 1/2, 3/6, 4/8, and 7/5 all have 17 triangles each. – 2011-01-26
-
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