Premium
A sufficient condition for equality of edge‐connectivity and minimum degree of a graph
Author(s) -
Goldsmith Donald L.,
Entringer Roger C.
Publication year - 1979
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/jgt.3190030307
Subject(s) - neighbourhood (mathematics) , combinatorics , mathematics , degree (music) , vertex (graph theory) , graph , connectivity , bound graph , order (exchange) , discrete mathematics , graph power , line graph , physics , mathematical analysis , finance , acoustics , economics
Let G be a connected graph of order p ≥ 2, with edge‐connectivity κ 1 ( G ) and minimum degree δ( G ). It is shown her ethat in order to obtain the equality κ 1 ( G ) = δ( G ), it is sufficient that, for each vertex x of minimum degree in G , the vertices in the neighbourhood N ( x ) of x have sufficiently large degree sum. This result implies a previous result of Chartrand, which required that δ( G ) ≥ [ p /2].