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

I'm working on the 17x17 challenge, and this sub-problem has come up. I have one solution to this problem that you can see here:

For some complex reasons (that I can elaborate on if needed) I know that this graph is unique if I add the following constraint: There has to exist a subset of at least 6 5 nodes that are not connected to each other and are not individually part of a 3-cycle. In the graph above, any 5-set of pink nodes satisfies this constraint. What I do not know is if it is still unique when I remove this extra constraint.

I'm coming from a CS background so I may be missing something basic from a graph theory perspective. Any references that may help me either prove that this is the case, disprove it by producing one or more different graphs or (even better) by producing all possible alternative solutions would be deeply appreciated.

EDIT: On closer examination, it seems the graph contains a double Hamiltonian circuit that uses every edge. No idea if this is relevant. [not interesting]

share|improve this question
1  
Re: your edit, this is an Eulerian circuit, and every 4-regular connected graph has one. So, nothing special there, I'm afraid. –  JBL Jan 25 '11 at 20:11
    
Ah I see. Cheers. Do you know by any chance if a 16-connected 17-node graph can be partitioned into 4 4-connected ones? –  user11898 Jan 25 '11 at 21:12
    
Thinking about it more, does every Eulerian circuit of a 4-connected graph have to pass from the original vertex at exactly the middle of the tour? –  user11898 Jan 26 '11 at 8:00
    
If by "4-connected" you mean "4-regular," the answer is "no." Having two edge-disjoint Hamiltonian paths is stronger than having an Eulerian path. (Example: take two 4-regular graphs of different sizes and remove an edge from each. Now draw two new edges, each joining a degree-3 vertex from one of your graphs to a degree-3 vertex from the other. The resulting graph is 4-regular, but every Hamiltonian circuit (if any exist) passes through the two edges we've just created, and the two visits to the vertices we've tinkered with cannot be equally spaced in the Eulerian cycle.) –  JBL Jan 26 '11 at 14:34
    
4-regular is correct. So the above graph, having two edge-disjoint Hamiltonian cycles, is not typical of every 4-regular graph then, do I get it right? [on the question in my first response, nevermind, I've solved it in the affirmative] –  user11898 Jan 26 '11 at 15:26
show 1 more comment

4 Answers

up vote 6 down vote accepted

Yes, here are some

Graph 1, order 17. 0 : 5 8 12 13; 1 : 6 9 13 16; 2 : 7 10 13 15; 3 : 8 9 14 15; 4 : 9 10 11 12; 5 : 0 11 15 16; 6 : 1 10 14 16; 7 : 2 11 13 14; 8 : 0 3 12 14; 9 : 1 3 4 15; 10 : 2 4 6 12; 11 : 4 5 7 16; 12 : 0 4 8 10; 13 : 0 1 2 7; 14 : 3 6 7 8; 15 : 2 3 5 9; 16 : 1 5 6 11;

Graph 2, order 17. 0 : 5 8 14 15; 1 : 6 9 15 16; 2 : 7 11 13 16; 3 : 8 9 10 13; 4 : 9 11 12 14; 5 : 0 10 11 15; 6 : 1 10 12 16; 7 : 2 12 13 15; 8 : 0 3 14 16; 9 : 1 3 4 15; 10 : 3 5 6 13; 11 : 2 4 5 16; 12 : 4 6 7 14; 13 : 2 3 7 10; 14 : 0 4 8 12; 15 : 0 1 5 7 9; 16 : 1 2 6 8 11;

Graph 3, order 17. 0 : 5 7 11 13; 1 : 6 8 13 15; 2 : 7 9 10 15; 3 : 8 10 14 16; 4 : 9 11 12 14; 5 : 0 11 15 16; 6 : 1 12 13 16; 7 : 0 2 10 13; 8 : 1 3 14 15; 9 : 2 4 12 15; 10 : 2 3 7 16; 11 : 0 4 5 14; 12 : 4 6 9 16; 13 : 0 1 6 7; 14 : 3 4 8 11; 15 : 1 2 5 8 9; 16 : 3 5 6 10 12;

Graph 4, order 17. 0 : 5 7 14 16; 1 : 6 8 12 13; 2 : 7 9 10 12; 3 : 8 10 11 15; 4 : 9 11 13 14; 5 : 0 13 15 16; 6 : 1 11 12 16; 7 : 0 2 10 14; 8 : 1 3 14 15; 9 : 2 4 12 15; 10 : 2 3 7 13; 11 : 3 4 6 16; 12 : 1 2 6 9; 13 : 1 4 5 10; 14 : 0 4 7 8; 15 : 3 5 8 9; 16 : 0 5 6 11;

Graph 5, order 17. 0 : 5 7 11 13; 1 : 6 8 12 15; 2 : 7 9 10 15; 3 : 8 10 14 16; 4 : 9 12 13 16; 5 : 0 11 15 16; 6 : 1 11 12 14; 7 : 0 2 10 13; 8 : 1 3 13 15; 9 : 2 4 14 15; 10 : 2 3 7 16; 11 : 0 5 6 14; 12 : 1 4 6 16; 13 : 0 4 7 8; 14 : 3 6 9 11; 15 : 1 2 5 8 9; 16 : 3 4 5 10 12;

Graph 6, order 17. 0 : 5 7 12 13; 1 : 6 10 13 16; 2 : 7 8 14 15; 3 : 8 9 10 12; 4 : 9 11 13 14; 5 : 0 10 11 15; 6 : 1 12 15 16; 7 : 0 2 14 16; 8 : 2 3 11 12; 9 : 3 4 13 15; 10 : 1 3 5 14; 11 : 4 5 8 16; 12 : 0 3 6 8; 13 : 0 1 4 9; 14 : 2 4 7 10; 15 : 2 5 6 9; 16 : 1 6 7 11;

Graph 7, order 17. 0 : 5 7 11 14; 1 : 6 11 13 15; 2 : 7 8 12 13; 3 : 8 9 14 15; 4 : 9 10 11 12; 5 : 0 10 13 16; 6 : 1 12 14 16; 7 : 0 2 12 15; 8 : 2 3 11 16; 9 : 3 4 13 14; 10 : 4 5 15 16; 11 : 0 1 4 8; 12 : 2 4 6 7; 13 : 1 2 5 9; 14 : 0 3 6 9; 15 : 1 3 7 10; 16 : 5 6 8 10;

Graph 8, order 17. 0 : 5 7 13 14; 1 : 6 11 13 15; 2 : 7 8 10 12; 3 : 8 9 15 16; 4 : 9 10 11 14; 5 : 0 11 12 16; 6 : 1 12 14 15; 7 : 0 2 10 13; 8 : 2 3 14 16; 9 : 3 4 12 13; 10 : 2 4 7 15; 11 : 1 4 5 16; 12 : 2 5 6 9; 13 : 0 1 7 9; 14 : 0 4 6 8; 15 : 1 3 6 10; 16 : 3 5 8 11;

share|improve this answer
1  
It seems to me that graph 1 satisfies the conditions, and it has seven triangles, whereas it seems the graph given in the original post only has three triangles, so they're not isomorphic. I haven't checked your other examples. –  Zsbán Ambrus Jan 26 '11 at 10:02
    
Thank you very much for these. I want to visualise and check them but for the moment I'll accept the answer. May I inquire on the method you used to produce these? cheers –  user11898 Jan 27 '11 at 11:02
1  
Brendan McKay's program "geng" generates graphs with various properties... I just ran geng -d4 -f 17 (-d4 means minimum degree 4, -f means no 4-cycles and 17 is the number of vertices) –  Gordon Royle Jan 27 '11 at 13:43
    
wow, that's awesome. Thanks again! –  user11898 Jan 27 '11 at 16:23
1  
Actually it is complete - at first I just ran it for a few minutes and grabbed the first few, but I ran it to completion and there were no more... –  Gordon Royle Jan 27 '11 at 23:20
show 2 more comments

I don't have the reputation to comment here, but that last example of a circulant graph by Gerry has plenty of 4-cycles... e.g., take 1,5,6,2. Sorry I don't have anything constructive to answer.

share|improve this answer
add comment

I don't know whether this one is different from the one you have, but one way to make such a graph is to start with a (convex) 17-gon (so there are your 17 nodes, and two edges at each) and then draw an edge connecting each vertex to the ones four vertices away in either direction (two more edges at each vertex, making 4 in all).

EDIT: Oops! My thanks to those who pointed out the error here, and my apologies for posting this incorrect answer.

share|improve this answer
4  
Thanks for the thought. I drew what you suggested here You can notice an instance of a 4-cycle in red. I drew a [5-distance]( docs.google.com/drawings/…) one as well. Thinking about it more, no such pattern can produce a 4-cycle free graph as any two consecutive nodes in the periphery will be linked, and they will each link to one of two consecutive nodes which will also be linked to each other, hence, 4-cycle. –  user11898 Jan 25 '11 at 14:02
add comment

Here's an idea. Start with a list of all the 4-subsets of vertices and a complete graph. Start removing edges greedily to break many 4 cliques while keeping the degrees high. At some point you will have a fairly dense graph with a hopefully short list of 4-cycles remaining. You can then try nongreedy or exhaustive algorithms to produce a subgraph with no 4 cycles.

Gerhard "Ask Me About System Design" Paseman, 2011.01.25

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.