3
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ In Q3 do you mean all chords at once, or maybe different hamcycle for each chord? $\endgroup$
    – Brendan McKay
    Commented May 21, 2019 at 12:16
  • $\begingroup$ @BrendanMcKay I mean all chords at once, I have edited the question $\endgroup$
    – EGME
    Commented May 21, 2019 at 12:27
  • $\begingroup$ 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 ... $\endgroup$
    – EGME
    Commented May 21, 2019 at 12:36
  • $\begingroup$ I think Q2 is true, sounds very familiar to a homework problem in graph theory... $\endgroup$
    – Per Alexandersson
    Commented May 21, 2019 at 14:28
  • $\begingroup$ @PerAlexandersson It would be excellent if you could provide a reference, or if the proof is easy, sketch it in an answer $\endgroup$
    – EGME
    Commented May 21, 2019 at 14:29

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
10
  • $\begingroup$ 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 ... $\endgroup$
    – EGME
    Commented May 21, 2019 at 14:34
  • $\begingroup$ Yes, see the explanation I added. $\endgroup$
    – Brendan McKay
    Commented May 21, 2019 at 14:39
  • $\begingroup$ It will be interesting to check for edge-3-colorability $\endgroup$
    – EGME
    Commented May 21, 2019 at 14:42
  • 1
    $\begingroup$ The graphs 28-1 and 40-1 are not 3-edge-colorable. $\endgroup$
    – LeechLattice
    Commented May 22, 2019 at 2:37
  • $\begingroup$ Thank you! Interesting, relatively few! $\endgroup$
    – EGME
    Commented May 22, 2019 at 7:04

You must log in to answer this question.

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