Let $G$ be a 3-connected cubic graph with a dominating circuit $C$, that is, a circuit such that all edges in $G$ have at least one endvertex in $C$. Let $D$ be another circuit and let the symmetric difference $C+D$ be the 2-regular graph induced by $E(C)\cup E(D)-E(C)\cap E(D)$. A chord of $C$ is an edge with both endvertices in $C$. A dominated vertex is a vertex not in $C$. The vertices in $C$ adjacent to a dominated vertex $v$ are the feet of $v$.
The question is as follows:
Question I:
Given dominating circuit $C$ in $G$ cubic 3-connected, is there a another circuit $D$ (OR under what conditions is this true) such that:
- $C+D$ is connected;
- $D$ contains all the endvertices of chords of $C$;
- if $D$ does not contain a foot of some dominated vertex $v$, then it contains $v$.
We may even ask that:
- $D$ does not contain some foot of every dominated vertex.
We will call D a ${\it vertocircuit}$ or ${\it vertocycle}$ of $C$ (see ensuing discussion below in METAQUESTION). If condition (4) is satisfied, then we call it a ${\it total\ vertocycle}$.
Note the following: a stable circuit $C$ in a cubic graph $G$ is a circuit such that there is no distinct circuit $C’$ of $G$ which contains $V(C)$ (if such circuit exists, it is called an extension of $C$). Stable circuits exist, they were discovered by Fleischner, and further studied by Kochol, Hägglund, Markström, among others. So the question asks for an “alternative” to extensions in which $C$ and $D$ “exchange” some vertices. Clearly, this question is of particular relevance for stable cycles.
CONJECTURE [Vertocycle conjecture]: Any stable dominating circuit in a cubic 3-connected graph has a (total?) vertocircuit.
We would like the conjecture to be more general, but without the stability condition on $C$ (or some other condition), as Tommy Jensen points out, the conjecture is not true; the Möbius-Kantor graph is a counterexample (see here for information on the Möbius-Kantor graph: http://mathworld.wolfram.com/Moebius-KantorGraph.html). If $C$ is the usual Hamiltonian circuit in this graph, and $D$ is any other Hamiltonian circuit, their symmetric difference is not connected. One can check in small examples that are not Hamiltonian (the Petersen graph for example) that the conjecture holds there. So I wonder what is the right additional condition that might replace stability.
Question: Might the readers suggest a good condition to replace stability in the conjecture? Stability is hard to detect and little understood.
One might ask if a dominating circuit has a total vertocircuit, assuming it has a vertocircuit. In any case, if the conjecture is true, as it might appear to be, it might help settle some very old and well known graph theory open problems (again, see the reference for a quick introduction to the subject and follow the citation links within that article). All vertocycles of $C$ are strong semiextensions of $C$ (again, see the reference below and follow the citation links).
MO graphs are cubic graphs which have a chordless dominating circuit $O$. They were introduced to MathOverflow in this post:
A question about dominating circuits in cubic graphs
Brendan McKay already asks (personal communication):
Subquestion: Do MO graphs have a unique chordless dominating circuit?
If the vertocycle conjecture is true, this would imply a negative answer to this question. If the answer to this question is affirmative for any MO graph, I believe the vertocycle conjecture would be false (I need to give this more thought), although one could still try to find out if it is true when the dominating circuit is stable. In MO graphs, the dominating circuit $O$ is not stable. I will do some checking of this next week.
Stronger questions:
II. Given a dominating circuit $C$, an edge $e$ in $C$ and a ${\it chordal\ path}$ $f$ of $C$, is there a vertocycle of $C$ containing $e, f$?
III. Given any set of chordal paths cotaining all dominated vertices of $C$, is there a total vertocycle that contains these chordal paths?
One can play with these kinds of conditions to obtain a number of stronger questions. I picked just these two as an illustration. They are of particular interest to me. I have no idea if they would be true or not. I will try to do some checking soon.
META QUESTION: How would you call these cycles? They are already strong semiextensions (see 1 for references about this, I will try to complete definitions little by little here, but this is not critical at the moment to understand the problem), but they are a special kind of them. I like the term “swappers” or “exchanger cycles”. Anyway, please do suggest. I believe that for now I will settle for the term "vertocycle" or "vertocircuit" unless my Latin etimology fails me.
COMPUTATIONAL NOTE: I now have a program that looks into this to some extent. I am able to find all “swappers” for the stable circuits in the snarks (see 1 for definitions) shown and discussed in 1 below. So for example, for the stable circuit in the top left snark on page 2542 of 1 there are 25 possible “exchanger cycles” or "vertocycles ". Of the 25, 18 are total. I have now checked the connectivity requirement and corrected some errors and updated the file which contains them. I hope there are no remaining mistakes in the algorithm or in the now visual inspection that I carried out. But I will do another check when I have time, and finish writing the algorithm. Here is a link with a document with the 25 possible vertocycles... I don't know if the link works ... perhaps you need a gmail account.
https://drive.google.com/file/d/1DRZB5rpPD-aFBjnc-1Bdhg_EOTUZShG1/view?usp=sharing
In any case, here is one which is total:
... and $C+D$
And here is one that looks like a vertocycle (and it even leaves a dominated vertex unused) but it is not, since OUTER GREY cycle + RED is not connected:
and $C+D$ with different components in different colors (I just noted that the rendering program is buggy so edge 15-16 should be grey, not red, I can't seem to get this fixed):
I will try also to produce a web page with an interactive app that will let you inspect each of the 21 and the symmetric differences.
1 Hägglund, J. and Markstöm, K., On stable cycles and cycle double covers on graphs with large circumference, ${\it Discrete\ Mathematics}$ 312 (2012) 2540-2544
