Premium
Degree sums and graphs that are not covered by two cycles
Author(s) -
Saito Akira
Publication year - 1999
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199909)32:1<51::aid-jgt5>3.0.co;2-l
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , discrete mathematics , bound graph , symmetric graph , graph power , line graph , voltage graph
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. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 51–61, 1999