Does every 4-regular graph contain a cycle of length (number of edges in the cycle) $1 (\mod3)$? Are there only finitely many exceptions?
I suspect such cycles exist for most 3-regular graphs but 4-regularity is enough for what I'm investigating.
$\begingroup$
$\endgroup$
4
asked Jul 22, 2010 at 4:12
-
$\begingroup$ I guess you want the graph to be simple. Take two vertices connected by 4 edges. $\endgroup$– Tony HuynhCommented Jul 22, 2010 at 12:58
-
$\begingroup$ Yes thanks for the correction, simple and connected. $\endgroup$– Gjergji ZaimiCommented Jul 22, 2010 at 13:30
-
$\begingroup$ Do you mean simple cycle? $\endgroup$– Grigory YaroslavtsevCommented Jul 22, 2010 at 13:39
-
$\begingroup$ Yes, the cycles are simple, too. $\endgroup$– Gjergji ZaimiCommented Jul 22, 2010 at 13:46
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
According to this paper, N. Dean et al. have shown that if a simple graph G
- is 2-connected,
- has minimum degree at least 3, and
- is not isomorphic to the Petersen graph,
then G contains a cycle of length 1 mod 3.
Now consider any 4-regular graph H. If I'm not mistaken, it's fairly easy to show that H contains a subgraph G such that two nodes of G have degree 3, all other nodes of G have degree 4, and G is 2-connected. Clearly G can't be the Petersen graph, and thus the above theorem implies that G (and therefore also H) contains a cycle of length 1 mod 3.
Edit: Here is how would construct G given H. Recall that H has a 2-factorisation, i.e., it consists of cycles such that each node of H is "covered" by exactly 2 cycles. If there are no articulation points in H, the claim is clear. Otherwise consider the block tree of H and pick a biconnected component K that contains only one articulation point; let x be the articulation point. Consider the subgraph K' = K − x; this graph consists of one path P and a set of cycles, and each node of K' is covered by either P and one cycle or exactly 2 cycles. It may be the case that K' contains articulation points. However, each articulation point is an endpoint of a bridge, and each bridge is an edge of P. Remove all bridges and let G be one of the connected components in the resulting bridgeless graph.
-
$\begingroup$ Finding your subgraph G is easy, as you say: if H is not biconnected, find a block with only one articulation point adjacent to it, and let G be the remaining vertices in that block. If H is biconnected, you can just use H in place of G, since you don't actually require the existence of the two degree-three vertices, but if you really want them you can remove the last ear in an ear decomposition. $\endgroup$ Commented Jul 27, 2010 at 3:14
-
$\begingroup$ @David: I think you need to be a bit more careful in the construction of G; removing the articulation point may create new articulation points. I added a sketch of the construction of G above; essentially just do what you said, remove all bridges, and pick one of the components. $\endgroup$ Commented Jul 27, 2010 at 14:44
$\begingroup$
$\endgroup$
2
This paper shows that such graphs may lack a cycle of a particular length:
Some 4-valent, 3-connected, planar, almost pancyclic graphs
S. A. Choudum
Discrete Mathematics, Volume 18, Issue 2, 1977, Pages 125-129
Abstract:
For each positive integer k (≠ 5,6), a 4-valent, 3-connected, planar graph, having cycles of all (possible) lengths except k is constructed.
answered Jul 22, 2010 at 13:13
-
1$\begingroup$ This sounds interesting, however as I understand it these graphs do not provide a counterexample, that is they have some cycle of length 3m+1 for some m. $\endgroup$ Commented Jul 22, 2010 at 13:45
-
$\begingroup$ Gjergij: Yes, that is correct. While not noted above there is quite a large literature about the existence (or lack of existence) of cycles in graphs, in particular mod m. Perhaps things are easier in the case that interests you for planar graphs. $\endgroup$ Commented Jul 22, 2010 at 21:37