Independence, irredundance, degrees and chromatic number in graphs (Q1861218)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Independence, irredundance, degrees and chromatic number in graphs |
scientific article; zbMATH DE number 1882155
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Independence, irredundance, degrees and chromatic number in graphs |
scientific article; zbMATH DE number 1882155 |
Statements
Independence, irredundance, degrees and chromatic number in graphs (English)
0 references
16 March 2003
0 references
For a graph \(G\), let \(\beta\), IR, \(\delta\) and \(\Delta\) denote the independence number, the upper irredundance number, and the minimum and maximum degree of \(G\). It is proved that if \(\Delta\neq 0\), then \(\text{IR}\leq n/(1+\delta/\Delta)\) and \(\text{IR}-\beta\leq (\Delta- 2)n/(2\Delta)\). The second inequality proves a conjecture of Rautenbach.
0 references
dominating sets
0 references
independence number
0 references
