The structure of graphs with no cycles of length 0 (mod 3)

Abstract

We examine the structure of graphs that have no cycles of length 0 (mod 3). We show that, if G is a simple 2-connected graph with no cycles of length 0 (mod 3), then G has two adjacent degree two vertices or G has two nonadjacent degree two vertices with the same neighborhood. Using this result, it follows that if G is a simple graph with no cycles of length 0 (mod 3), then for every induced subgraph H of G, the modularity of H, defined as the number of even independent sets minus the number of odd independent sets, is either −1, 0, or 1.