Cycles of length 2 modulo 3 in graphs

✍ Scribed by Akira Saito

• Publisher: Elsevier Science
• Year: 1992
• Tongue: English
• Weight: 274 KB
• Volume: 101
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(92)90609-j

✦ Synopsis

Saito, A., Cycles of length 2 modulo 3 in graphs, Discrete Mathematics 101 (1992) 285-289. We prove that if a graph G of minimum degree at least 3 has no cycle of length 2 (mod 3), then G has an induced subgraph which is isomorphic to either K4 or Ks,s. The above result together with its relatively short proof gives a short proof to the result by Dean et al. that every 2-connected graph of minimum degree at least 3, except for K4 and K,,, (n 3 3), has a cycle of length 2 (mod3). Furthermore, it gives the following immediate corollary: Every cubic connected graph except for K4 and K3,3 has a cycle of length 2 (mod 3).

For integers a and b a cycle is said to be an (a mod 6)-cycle if its length is a (mod b). In [l] it has been conjectured that every graph of minimum degree at least 3 contains a (0 mod 3)-cycle. This conjecture has recently been proved by Chen and Saito [3].

On the other hand, when we consider (1 mod 3)-cycles and (2 mod 3)-cycles we find that the situation is different. For i = 1, 2, there are infinitely many graphs of minimum degree at least 3 which have no (i mod 3)-cycle. For example, neither K4 nor K3,,, has a (2 mod 3)-cycle. Then a graph all of whose blocks are subgraphs of K4 or K3,n has no (2 mod 3)-cycle. In a similar way we can construct infinitely many graphs without a (1 mod 3)-cycle, using the Petersen graph.

However, if we put additional assumptions, we may be able to assure the existence of (2 mod 3)-cycles (resp. (1 mod 3)-cycles), possibly with a few exceptions. In fact Dean, Kaneko, Ota and Toft [4] have proved the following theorem.

Theorem A (Dean et al. [4]). Let G be a 2-connected graph of minimum degree at least 3.