Bicritical domination

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

doi:10.1016/j.disc.2005.09.013

Bicritical domination

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

Research output: Contribution to journal › Article › peer-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 language	English
Pages (from-to)	18-32
Number of pages	15
Journal	Discrete Mathematics
Volume	305
Issue number	1-3
DOIs	https://doi.org/10.1016/j.disc.2005.09.013
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

Access to Document

10.1016/j.disc.2005.09.013

Cite this

@article{df0678232dc341fd8066959984582eed,

title = "Bicritical domination",

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.",

keywords = "Bounds, Diameter, Domination, Vertex bicritical domination, Vertex critical domination",

author = "Brigham, \{Robert C.\} and Haynes, \{Teresa W.\} and Henning, \{Michael A.\} and Rall, \{Douglas F.\}",

year = "2005",

month = dec,

day = "6",

doi = "10.1016/j.disc.2005.09.013",

language = "English",

volume = "305",

pages = "18--32",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Bicritical domination

AU - Brigham, Robert C.

AU - Haynes, Teresa W.

AU - Henning, Michael A.

AU - Rall, Douglas F.

PY - 2005/12/6

Y1 - 2005/12/6

N2 - 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.

AB - 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.

KW - Bounds

KW - Diameter

KW - Domination

KW - Vertex bicritical domination

KW - Vertex critical domination

UR - https://www.scopus.com/pages/publications/28544440152

U2 - 10.1016/j.disc.2005.09.013

DO - 10.1016/j.disc.2005.09.013

M3 - Article

AN - SCOPUS:28544440152

SN - 0012-365X

VL - 305

SP - 18

EP - 32

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Bicritical domination

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this