Bicritical domination

Robert C. Brigham, Teresa W. Haynes, Michael A. Henning, Douglas F. Rall

Research output: Contribution to journalArticlepeer-review

26 Citations (Scopus)

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 languageEnglish
Pages (from-to)18-32
Number of pages15
JournalDiscrete Mathematics
Volume305
Issue number1-3
DOIs
Publication statusPublished - 6 Dec 2005
Externally publishedYes

Keywords

  • Bounds
  • Diameter
  • Domination
  • Vertex bicritical domination
  • Vertex critical domination

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Bicritical domination'. Together they form a unique fingerprint.

Cite this