Restrained domination in trees

Gayla S. Domke; Johannes H. Hattingh; Michael A. Henning; Lisa R. Markus

doi:10.1016/S0012-365X(99)00036-9

Restrained domination in trees

Gayla S. Domke, Johannes H. Hattingh, Michael A. Henning, Lisa R. Markus

Research output: Contribution to journal › Article › peer-review

44 Citations (Scopus)

Abstract

Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex not in S is adjacent to a vertex in S and to a vertex in V - S. The restrained domination number of G, denoted by γr(G), is the smallest cardinality of a restrained dominating set of G. We show that if T is a tree of order n, then γr(T)≥[(n + 2)/3]. Moreover, we constructively characterize the extremal trees T of order n achieving this lower bound.

Original language	English
Pages (from-to)	1-9
Number of pages	9
Journal	Discrete Mathematics
Volume	211
Issue number	1-3
DOIs	https://doi.org/10.1016/S0012-365X(99)00036-9
Publication status	Published - 28 Jan 2000
Externally published	Yes

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/S0012-365X(99)00036-9

Cite this

@article{ec567eba0a8d40bc8cbe5315e8e02434,

title = "Restrained domination in trees",

abstract = "Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex not in S is adjacent to a vertex in S and to a vertex in V - S. The restrained domination number of G, denoted by γr(G), is the smallest cardinality of a restrained dominating set of G. We show that if T is a tree of order n, then γr(T)≥[(n + 2)/3]. Moreover, we constructively characterize the extremal trees T of order n achieving this lower bound.",

author = "Domke, {Gayla S.} and Hattingh, {Johannes H.} and Henning, {Michael A.} and Markus, {Lisa R.}",

year = "2000",

month = jan,

day = "28",

doi = "10.1016/S0012-365X(99)00036-9",

language = "English",

volume = "211",

pages = "1--9",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Restrained domination in trees

AU - Domke, Gayla S.

AU - Hattingh, Johannes H.

AU - Henning, Michael A.

AU - Markus, Lisa R.

PY - 2000/1/28

Y1 - 2000/1/28

N2 - Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex not in S is adjacent to a vertex in S and to a vertex in V - S. The restrained domination number of G, denoted by γr(G), is the smallest cardinality of a restrained dominating set of G. We show that if T is a tree of order n, then γr(T)≥[(n + 2)/3]. Moreover, we constructively characterize the extremal trees T of order n achieving this lower bound.

AB - Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex not in S is adjacent to a vertex in S and to a vertex in V - S. The restrained domination number of G, denoted by γr(G), is the smallest cardinality of a restrained dominating set of G. We show that if T is a tree of order n, then γr(T)≥[(n + 2)/3]. Moreover, we constructively characterize the extremal trees T of order n achieving this lower bound.

UR - http://www.scopus.com/inward/record.url?scp=0005312706&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(99)00036-9

DO - 10.1016/S0012-365X(99)00036-9

M3 - Article

AN - SCOPUS:0005312706

SN - 0012-365X

VL - 211

SP - 1

EP - 9

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Restrained domination in trees

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this