Cycles of length 2 modulo 3 in graphs
Cycles of length 2 modulo 3 in graphs
复制标题
DOI：
10.1016/0012-365x(92)90609-j
复制
发表时间：
1992-05
期刊：
影响因子：
--
通讯作者：
Akira Saito
中科院分区：
文献类型：
--
作者：
Akira Saito
本文证明了：如果最小度至少为3的图G没有长度为2（mod 3）的圈，则G有一个导出子图同构于K4或K3，3.上述结果及其较短的证明对Dean等人的结果给出了一个较短的证明：除K4和K3，n（n <$3）外，任何最小度至少为3的2-连通图都有一个长度为2（mod 3）的圈.此外，还给出了如下直接推论：除K4和K3，3外，每一个三次连通图都有一个长为2（mod 3）的圈.
We prove that if a graphGof minimum degree at least 3 has no cycle of length 2 (mod 3), thenGhas an induced subgraph which is isomorphic to eitherK4orK3,3. 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 forK4andK3,n(n⩾ 3), has a cycle of length 2 (mod 3). Furthermore, it gives the following immediate corollary: Every cubic connected graph except forK4andK3,3has a cycle of length 2 (mod 3).