Premium
A linear vizing‐like relation between the size and the domination number of a graph
Author(s) -
Rautenbach Dieter
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(199908)31:4<297::aid-jgt4>3.0.co;2-1
Subject(s) - mathematics , combinatorics , domination analysis , graph , upper and lower bounds , discrete mathematics , vertex (graph theory) , mathematical analysis
We prove m ≤ Δ n − (Δ + 1)γ for every graph without isolated vertices of order n , size m , domination number γ and maximum degree Δ ≥ 3. This generalizes a result of Fisher et al., CU‐Denver Tech Rep, 1996] who obtained the given bound for the case Δ = 3. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 297–302, 1999
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom