9
$\begingroup$

Let $G$ be a bridgeless cubic graph. I am interested in such graphs where all 2-factors are isomorphic (as graphs), i.e. have the same partition as cycle type. We'll say that this partition is realized by the graph.
Apart from the trivial $K_4$ and $K_{3,3}$, an example is the Petersen graph realizing $(5,5)$, as all of its 2-factors are of type $(5,5)$. We can easily derive from it a 2-connected graph with a unique 2-factor, of type $(12, 5,5)$, by taking two copies and adding the blue vertices and edges.
enter image description here

It is in fact straightforward to see here that both "inner pentagrams" must belong to any 2-factor.

In view of this kind of construction, it doesn't seem of high interest to ask which partitions can be realized by 2-connected graphs. But it is much more interesting to look at 3-connected graphs.
It is not at all obvious for instance that there are 3-connected graphs which have Hamilton cycles as their only 2-factors. The following construction gives one for $n=26$:

enter image description here
In the Petersen graph $P$, there are triples of edges with pairwise distance $3$. If we add vertices $a,b,c$ on each of the edges of such a triple (see picture), now take a second instance of this graph and add three edges $aa',bb',cc'$, we'll come up with a 3-connected graph $G$ whose only 2-factors are H-cycles, i.e. it realizes the partition $(26)$. This is because $a,b,c$ cannot be all contained in a 2-factor of $P$, so there must be two of $aa',bb',cc'$ contained in any 2-factor of $G$, and from there it is easy to check that such a 2-factor cannot contain a $C_5$ of $P$, i.e. it must pass through all vertices.
EDIT: We can realize other types $(n)$ by replacing $P'$ by certain other graphs:

  • $n=14$ by just adding one vertex at which $a',b',c'$ concur.
  • $n=16$ by using instead a $K_3$ with vertices $a',b',c'$
  • $n=20$ by using a $K_4$ with $a',b',c'$ added on the edges of one of its triangles
  • ${n=22}$ by using a $K_{3,3}$ with $a',b',c'$ added on the edges of one of its 1-factors [edited again - this one isn't hamiltonian, but has all its 2-factors of type $(17,5)$]
  • for $n=36$ we can realize type $(n)$ as follows: start with two copies $P$ and $P'$ as above, join the three outgoing edges of $P$ (call them "blue edges") to the blue vertices and the three outgoing edges of $P'$ (call them "red edges") to the red vertices of this graph:
    enter image description here
    As above, any 2-factor of $G$ must contain exactly two of the red edges, and it is clear that there cannot be a smaller cycle in it, by checking all paths between two red vertices. On the other hand, several H-cycles obviously exist.
  • Replacing the central vertex by a small triangle doesn't change anything in terms of 2-factors, so the new graph realizes the partition (38). In fact, it looks like many (or, to be cautious, let's say several) graphs can be inscribed here instead, as long as they have a H-path between some two of the three 'corners', and as no other path exists between any two 'corners' such that the (graph induced on the) remaining vertices have a 2-factor. Believe it or not... inserting another Petersen graph here (with the three outgoing edges as above) would do $\implies$ a graph for $ n=48$ !

The general question:

  • Which partitions (= types) can be realized by 3-connected graphs?
  • Are there constructions that yield infinite families of such graphs (e.g. Hamiltonian graphs like the above one) ?
$\endgroup$
  • $\begingroup$ I'm a bit confused since your examples have 2-cuts (the two points of attachment of $A$ or $B$. $\endgroup$ – Brendan McKay Aug 2 '14 at 1:21
  • $\begingroup$ @BrendanMcKay oops, sure enough... I'll have to think through that again! $\endgroup$ – Wolfgang Aug 2 '14 at 8:17
  • $\begingroup$ @BrendanMcKay I have edited. After all, it looks like 3-connected graphs with that property are not that frequent - especially non Hamiltonian ones. $\endgroup$ – Wolfgang Aug 3 '14 at 8:24
  • $\begingroup$ $K_4$ and $K_{3,3}$ yield only type $(n)$. I suspect such graphs a very rare but I don't see how to characterise them. One cute thing: if you have a cubic graph and you know for sure it has only type $(n)$, you can find a hamiltonian cycle in polynomial time. $\endgroup$ – Brendan McKay Aug 4 '14 at 13:09
  • $\begingroup$ @BrendanMcKay Let the $K_{3,3}$ have vertex sets x1,y1,z1 and x2,y2,z2, further a' on edge x1x2 etc. Wlog a' and b' are on the 2-factor coming from P (containing a H-path a-...-c-...-b of P), then its cycle can be completed by a'-x1-y2-b', and the 5-cycle c'-z1-x2-y1-z2-c' covers the remaining vertices. That is, type (17,5). :( $\endgroup$ – Wolfgang Aug 4 '14 at 15:28
3
$\begingroup$

If you replace a vertex of the Petersen graph with a $K_{2,3}$ in the obvious fashion, then this gives a graph on 14 vertices with 12 two-factors all of type $(5,9)$.

Also there's one on 16 vertices obtained from Petersen by a different vertex-replacement.

Graph with isomorphic 2-factors

I'm sure you can find more similar ones.

$\endgroup$
  • $\begingroup$ Up to 18 vertices, the only types that I have found are (5, n-5) and (n) in an exhaustive search. I am running n=20 but I am too lazy to optimise the program, so will just wait till tomorrow for the outcome. $\endgroup$ – Gordon Royle Aug 5 '14 at 9:06
  • $\begingroup$ I just noticed that your (5,11) graph can be built from a $K_4$ (vertices 0,1,2,6) with three vertices (3,4,5) added on the edges adjacent to 6, on one side; and a $K_{3,3}$ (vertex sets 10,13,15 and 11,12,14) with three vertices (7,8,9) added on the edges of one of its 1-factors, on the other side; edges 3-7,4-8,5-9 then link both sides. This construction has a somewhat similar style to the ones I have suggested above - and of course still a 3-fold symmetry, like ALL graphs mentioned so far. Interesting!... $\endgroup$ – Wolfgang Aug 5 '14 at 12:24
  • $\begingroup$ If the vertices of Petersen are labelled as usual by $\binom52$, we can obtain $$.$$ - (a) type (9,17) by replacing vertices 12,34,35,45 by $K_{2,3}$'s (each $C_5$ of P has either one or three of these vertices) $$.$$ - (b) type (9,13) by replacing vertices 34,35,45 by $K_{2,3}$'s $$.$$ - similarly types (21,13) and (21,17) by replacing the complementary vertices of those in (a) and (b) by $K_{2,3}$'s $$.$$ - type (25,25) by replacing all ten vertices by $K_{2,3}$'s . $\endgroup$ – Wolfgang Aug 5 '14 at 14:20
  • $\begingroup$ Instead of $K_{2,3}$'s, we can also use one of the other "small graphs" as in my answer (except the $K_3$, as it will yield $C_3$'s) to obtain plenty of other types with two parts, e.g. type (65,65) by replacing all 10 vertices with P. BUT to obtain a type with more than two parts, a different "seed" would be needed instead of Petersen. I tend to doubt now that such a graph exists! Moreover: all cycles will be odd. What about even cycle lengths?? $\endgroup$ – Wolfgang Aug 6 '14 at 8:53
2
$\begingroup$

The examples given above already contain all the ingredients for a construction that yields indeed infinitely many graphs whose only 2-factors are H-cycles.

Start with an arbitrary rooted binary tree. We'll think from the leaves to the root.

  • Replace each leaf by the above graph $P$, leaving three "outgoing" edges.
  • Replace each node by the graph $T$ shown below, which accommodates a red and a blue triple of "incoming" edges, one for each branch/leaf, and has three "outgoing" edges (in green).
    enter image description here

  • Finally, replace the root by one of the four small graphs as above ($K_1,K_3,K_4$ or $P$, maybe some others are possible, too), accommodating the three "incoming" edges.

At each stage, two of the incoming red edges must belong to a 2-factor, and the same argument as for $n=36$ applies to show that the cycle (which must be, a forteriori, the same cycle as the one containing two of the blue incoming edges) must "continue beyond $T$". If the tree has $k$ leaves, this will result in a graph realizing $(n)$, where $n=13+(13+9)(k-1)+r=22k-9+r$ with $r\in\{1,3,7,13\}$ depending on the small graph chosen for the root.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.