Degree sums and graphs that are not covered by two cycles
Akira Saito · Journal of Graph Theory · 1999
For a graph G, let σ3(G) = min {degGx + degGy + degGz: {x, y, z} is an independent set in G}. Enomoto et al. [Enowoto et al., J Graph Theory 20 (1995), 419–422] have proved that the vertex set of a 2-connected graph G of order n with σ3(G) ≥ n is covered by two cycles, edges or vertices. Extending their result, we characterize the graphs of order n with σ3(G) ≥ n − 1 whose vertex set is not covered by two cycles, edges, or vertices. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 51–61, 1999