Premium
Decomposing graphs with girth at least five under degree constraints
Author(s) -
Diwan Ajit A.
Publication year - 2000
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(200004)33:4<237::aid-jgt4>3.0.co;2-a
Subject(s) - combinatorics , mathematics , degree (music) , vertex (graph theory) , graph , discrete mathematics , girth (graph theory) , physics , acoustics
Abstract We prove that the vertex set of a simple graph with minimum degree at least s + t − 1 and girth at least 5 can be decomposed into two parts, which induce subgraphs with minimum degree at least s and t , respectively, where s, t are positive integers ≥ 2. © 2000 John Wiley & Sons, Inc: J Graph Theory 33: 237–239, 2000