# Edge colorability and Hamiltonicity of certain classes of cubic graphs (MO graphs)

Let $$G$$ be a simple cubic graph (that is, 3-regular). A dominating circuit of $$G$$ is a circuit $$C$$ such that each edge of $$G$$ has an endvertex in $$C$$. The circuit $$C$$ is chordless if no edge which is not in $$C$$ has both endvertices in $$C$$ (such edges are called chords of $$C$$). An {\it MO graph} is a simple cubic graph which has a chordless dominating circuit, and (UPDATED EDIT) in addition, two edges incident with a vertex not in the dominating circuit cannot be attached to consecutive vertices in the dominating circuit.

QUESTION 1: Are MO graphs edge-3-colorable?

QUESTION 2: Are MO graphs Hamiltonian? An affirmative answer to this question implies an affirmative answer to the first one.

Computer generated experiments with randomly generated MO graphs, with fairly sizable graphs and thousands of them, suggest that the answer to both questions is YES. I would hope that at least question 1 can be settled. Question 2 looks hard. I have tried graphs with up to 100 claws with the 3-vertex off the dominating circuit, so that is 400 vertices.

A related question is the following:

QUESTION 3: What cubic Hamiltonian graphs with a Hamiltonian circuit $$C$$ have Hamiltonian circuits that contain all chords of $$C$$ in the same Hamiltonian circuit? Is there an effective characterization of these? Such a characterization would maybe allow one to settle question 2.

• In Q3 do you mean all chords at once, or maybe different hamcycle for each chord? May 21, 2019 at 12:16
• @BrendanMcKay I mean all chords at once, I have edited the question
– EGME
May 21, 2019 at 12:27
• The reason for calling the graphs MO is as follows: I think of the dominating circuit as O, and the claws with all edges off the dominating circuit as M’s. MO are also the initials of a graph theorist ... I believe I mentioned this in an old paper ...
– EGME
May 21, 2019 at 12:36
• I think Q2 is true, sounds very familiar to a homework problem in graph theory... May 21, 2019 at 14:28
• @PerAlexandersson It would be excellent if you could provide a reference, or if the proof is easy, sketch it in an answer
– EGME
May 21, 2019 at 14:29

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.

• Thank you! But wait, are these graphs simple? I see in the first one there is a 2,3,4; second one, 2,3,8; third 2,7,8 ... or am I missing something? Sorry, not simple ... but I think i forgot one condition in my statement. The claws cannot be attached to consecutive vertices in the dominating circuit ... I will edit .. please confirm if this is the case ...
– EGME
May 21, 2019 at 14:34
• Yes, see the explanation I added. May 21, 2019 at 14:39
• It will be interesting to check for edge-3-colorability
– EGME
May 21, 2019 at 14:42
• The graphs 28-1 and 40-1 are not 3-edge-colorable. May 22, 2019 at 2:37
• Thank you! Interesting, relatively few!
– EGME
May 22, 2019 at 7:04