Graphs Having (2 mod d)-Cycles |
| |
| Institution: | 1. Instituto de Matemática, Universidade Federal do Rio Grande do Sul, 91509-900 Porto Alegre, Brazil;2. Fakultät für Informatik, Technische Universität Chemnitz, 09107 Chemnitz, Germany;1. Laboratoire CEDRIC, CNAM, Paris, France;2. School of Engineering and Computing Sciences, Durham University, Durham, United Kingdom;3. Department of Informatics, University of Fribourg, Fribourg, Switzerland;1. School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu 610054, PR China;2. School of Sciences, Nanchang University, Nanchang, Jiangxi 330000, PR China |
| |
| Abstract: | It is known that if G is a graph with minimum degree δ at least d+1, then G has a cycle of length 2 mod d. We show that if G is also bipartite, then G has a cycle of length 2 mod 2d. Both these bounds are tight in terms of minimum degree. However, we show that if G is a graph with δ ≥ d and had neither Kd nor Kd,d as an induced subgraph, then G has a cycle of length 2 mod d. If G is also bipartite, then G has a cycle of length 2 mod 2d. If G is a 2-connected graph with δ ≥ d and is not congruent to Kd nor Kd,d' (for d' ≥ d) then G has a cycle of length 2 mod d. If G is also bipartite, then G has a cycle of length 2 mod 2d. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
