✦ LIBER ✦
Degree sums and graphs that are not covered by two cycles
✍ Scribed by Saito, Akira
- Publisher
- John Wiley and Sons
- Year
- 1999
- Tongue
- English
- Weight
- 127 KB
- Volume
- 32
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
For a graph G, let σ 3 (G) = min{deg G x + deg G y + deg G z: {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.