6
$\begingroup$

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]

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Re: your edit, this is an Eulerian circuit, and every 4-regular connected graph has one. So, nothing special there, I'm afraid. $\endgroup$
    – JBL
    Commented Jan 25, 2011 at 20:11
  • $\begingroup$ 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? $\endgroup$
    – user11898
    Commented Jan 25, 2011 at 21:12
  • $\begingroup$ 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? $\endgroup$
    – user11898
    Commented Jan 26, 2011 at 8:00
  • $\begingroup$ 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.) $\endgroup$
    – JBL
    Commented Jan 26, 2011 at 14:34
  • $\begingroup$ 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] $\endgroup$
    – user11898
    Commented Jan 26, 2011 at 15:26

4 Answers 4

Reset to default
6
$\begingroup$

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;

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Zsbán Ambrus
    Commented Jan 26, 2011 at 10:02
  • $\begingroup$ 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 $\endgroup$
    – user11898
    Commented Jan 27, 2011 at 11:02
  • 1
    $\begingroup$ 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) $\endgroup$
    – Gordon Royle
    Commented Jan 27, 2011 at 13:43
  • $\begingroup$ geng's documentation says that it can be used to 'Generate all graphs of a specified class'. Do I understand correctly that the list you gave is exhaustive? Cheers. $\endgroup$
    – user11898
    Commented Jan 27, 2011 at 16:37
  • 1
    $\begingroup$ 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... $\endgroup$
    – Gordon Royle
    Commented Jan 27, 2011 at 23:20
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ 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. $\endgroup$
    – user11898
    Commented Jan 25, 2011 at 14:02
0
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .