Return to Answer

This is a NEW EDITION using the condition that two edges incident with a vertex not in the dominating circuit cannot be attached to consecutive vertices in the dominating circuit.

I tried 100 million at random for each size $12, 16, \ldots, 48$ (it must be a multiple of 4). They were all hamiltonian except for 4 graphs on 28 vertices.

Vertices $0,1,\ldots,20$ in natural order are the dominating cycle. The neighbours of the other vertices are as follows.

Graph 1. 21 : 1 6 8; 22 : 16 18 20; 23 : 5 7 9; 24 : 4 17 19; 25 : 2 12 14; 26 : 0 3 10; 27 : 11 13 15;

Graph 2. 21 : 1 3 5; 22 : 13 15 17; 23 : 9 14 16; 24 : 7 12 20; 25 : 0 2 4; 26 : 6 10 19; 27 : 8 11 18;

Graph 3. 21 : 2 4 6; 22 : 10 12 17; 23 : 0 8 15; 24 : 1 3 5; 25 : 9 14 19; 26 : 11 16 18; 27 : 7 13 20;

Graph 4. 21 : 3 17 19; 22 : 4 18 20; 23 : 1 5 16; 24 : 2 6 14; 25 : 8 10 12; 26 : 9 11 13; 27 : 0 7 15;

These have not been tested for 3-edge-colourability.

This is a NEW EDITION using the condition that two edges incident with a vertex not in the dominating circuit cannot be attached to consecutive vertices in the dominating circuit.

I tried 200 million at random for each size $8, 12, \ldots, 48$ (it must be a multiple of 4). They were all hamiltonian except for 4 graphs on 28 vertices and 1 graph on 40 vertices.

Vertices $0,1,\ldots,3n/4-1$ in natural order are the dominating cycle. The neighbours of the other vertices are as follows.

Graph 28-1. 21 : 1 6 8; 22 : 16 18 20; 23 : 5 7 9; 24 : 4 17 19; 25 : 2 12 14; 26 : 0 3 10; 27 : 11 13 15;

Graph 28-2. 21 : 1 3 5; 22 : 13 15 17; 23 : 9 14 16; 24 : 7 12 20; 25 : 0 2 4; 26 : 6 10 19; 27 : 8 11 18;

Graph 28-3. 21 : 2 4 6; 22 : 10 12 17; 23 : 0 8 15; 24 : 1 3 5; 25 : 9 14 19; 26 : 11 16 18; 27 : 7 13 20;

Graph 28-4. 21 : 3 17 19; 22 : 4 18 20; 23 : 1 5 16; 24 : 2 6 14; 25 : 8 10 12; 26 : 9 11 13; 27 : 0 7 15;

Graph 40-1. 30 : 0 24 27; 31 : 1 25 28; 32 : 7 14 17; 33 : 4 6 23; 34 : 8 10 12; 35 : 9 11 16; 36 : 2 15 26; 37 : 18 20 22; 38 : 13 19 21; 39 : 3 5 29;

These have not been tested for 3-edge-colourability.

I am confident that there are many non-hamiltonian examples on larger sizes, but searching randomly quickly becomes a very inefficient way to find them.

There are at least 3 nonhamiltonian MO-graphs with 16 vertices.

In each case the chordless dominating cycle is 0-1-2-$\cdots$-11-0.

Then vertices 12,13,14,15 are each adjacent to 3 vertices of the cycle, thus:

(1) 2 3 4, 0 10 11, 6 7 8, 1 5 9

(2) 5 9 10, 2 3 8, 4 7 11, 0 1 6

(3) 3 4 10, 1 5 9, 2 7 8, 0 6 11

(1) means 12 is adjacent to 2, 3 and 4; 13 is adjacent to 0, 10 and 11, etc.

All of them have claws adjacent to consecutive vertices of the cycle.

I didn't check them for 3-edge colourings.

======

There are at least 65 nonhamiltonian MO-graphs with 20 vertices.

All of them have claws adjacent to consecutive vertices of the cycle.

I'll search more with the extra condition tomorrow.

This is a NEW EDITION using the condition that two edges incident with a vertex not in the dominating circuit cannot be attached to consecutive vertices in the dominating circuit.

I tried 100 million at random for each size $12, 16, \ldots, 48$ (it must be a multiple of 4). They were all hamiltonian except for 4 graphs on 28 vertices.

Vertices $0,1,\ldots,20$ in natural order are the dominating cycle. The neighbours of the other vertices are as follows.

Graph 1. 21 : 1 6 8; 22 : 16 18 20; 23 : 5 7 9; 24 : 4 17 19; 25 : 2 12 14; 26 : 0 3 10; 27 : 11 13 15;

Graph 2. 21 : 1 3 5; 22 : 13 15 17; 23 : 9 14 16; 24 : 7 12 20; 25 : 0 2 4; 26 : 6 10 19; 27 : 8 11 18;

Graph 3. 21 : 2 4 6; 22 : 10 12 17; 23 : 0 8 15; 24 : 1 3 5; 25 : 9 14 19; 26 : 11 16 18; 27 : 7 13 20;

Graph 4. 21 : 3 17 19; 22 : 4 18 20; 23 : 1 5 16; 24 : 2 6 14; 25 : 8 10 12; 26 : 9 11 13; 27 : 0 7 15;

These have not been tested for 3-edge-colourability.

There are at least 3 nonhamiltonian MO-graphs with 16 vertices.

In each case the chordless dominating cycle is 0-1-2-$\cdots$-11-0.

Then vertices 12,13,14,15 are each adjacent to 3 vertices of the cycle, thus:

(1) 2 3 4, 0 10 11, 6 7 8, 1 5 9

(2) 5 9 10, 2 3 8, 4 7 11, 0 1 6

(3) 3 4 10, 1 5 9, 2 7 8, 0 6 11

(1) means 12 is adjacent to 2, 3 and 4; 13 is adjacent to 0, 10 and 11, etc.

I didn't check them for 3-edge colourings.

There are at least 65 nonhamiltonian MO-graphs with 20 vertices.

There are at least 3 nonhamiltonian MO-graphs with 16 vertices.

In each case the chordless dominating cycle is 0-1-2-$\cdots$-11-0.

Then vertices 12,13,14,15 are each adjacent to 3 vertices of the cycle, thus:

(1) 2 3 4, 0 10 11, 6 7 8, 1 5 9

(2) 5 9 10, 2 3 8, 4 7 11, 0 1 6

(3) 3 4 10, 1 5 9, 2 7 8, 0 6 11

(1) means 12 is adjacent to 2, 3 and 4; 13 is adjacent to 0, 10 and 11, etc.

All of them have claws adjacent to consecutive vertices of the cycle.

I didn't check them for 3-edge colourings.

======

There are at least 65 nonhamiltonian MO-graphs with 20 vertices.

All of them have claws adjacent to consecutive vertices of the cycle.

I'll search more with the extra condition tomorrow.