Abstract
A graph G is domination bicritical if the removal of any pair of vertices decreases the domination number. Properties of bicritical graphs are studied. We show that a connected bicritical graph has domination number at least 3, minimum degree at least 3, and edge-connectivity at least 2. Ways of constructing a bicritical graph from smaller bicritical graphs are presented.
Original language | English |
---|---|
Pages (from-to) | 18-32 |
Number of pages | 15 |
Journal | Discrete Mathematics |
Volume | 305 |
Issue number | 1-3 |
DOIs | |
Publication status | Published - 6 Dec 2005 |
Externally published | Yes |
Keywords
- Bounds
- Diameter
- Domination
- Vertex bicritical domination
- Vertex critical domination
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics