Restrained domination in unicyclic graphs

Johannes H. Hattingh; Ernst J. Joubert; Marc Loizeaux; Andrew R. Plummer; Lucas Van Der Merwe

doi:10.7151/dmgt.1433

Restrained domination in unicyclic graphs

Johannes H. Hattingh, Ernst J. Joubert, Marc Loizeaux, Andrew R. Plummer, Lucas Van Der Merwe

Mathematics and Applied Mathematics

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

7 Citations (Scopus)

Abstract

Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V - S is adjacent to a vertex in S and to a vertex in V - S. The restrained domination number of G, denoted by yr(G), is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then yr(U) ≥ d n 3 e, and provide a characterization of graphs achieving this bound.

Original language	English
Pages (from-to)	71-86
Number of pages	16
Journal	Discussiones Mathematicae - Graph Theory
Volume	29
Issue number	1
DOIs	https://doi.org/10.7151/dmgt.1433
Publication status	Published - 2009

Keywords

Restrained domination
Unicyclic graph

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.7151/dmgt.1433

Cite this

@article{3d684442b0d8491da027083309236694,

title = "Restrained domination in unicyclic graphs",

abstract = "Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V - S is adjacent to a vertex in S and to a vertex in V - S. The restrained domination number of G, denoted by yr(G), is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then yr(U) ≥ d n 3 e, and provide a characterization of graphs achieving this bound.",

keywords = "Restrained domination, Unicyclic graph",

author = "Hattingh, {Johannes H.} and Joubert, {Ernst J.} and Marc Loizeaux and Plummer, {Andrew R.} and {Van Der Merwe}, Lucas",

year = "2009",

doi = "10.7151/dmgt.1433",

language = "English",

volume = "29",

pages = "71--86",

journal = "Discussiones Mathematicae - Graph Theory",

issn = "1234-3099",

publisher = "University of Zielona Gora",

number = "1",

}

TY - JOUR

T1 - Restrained domination in unicyclic graphs

AU - Hattingh, Johannes H.

AU - Joubert, Ernst J.

AU - Loizeaux, Marc

AU - Plummer, Andrew R.

AU - Van Der Merwe, Lucas

PY - 2009

Y1 - 2009

N2 - Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V - S is adjacent to a vertex in S and to a vertex in V - S. The restrained domination number of G, denoted by yr(G), is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then yr(U) ≥ d n 3 e, and provide a characterization of graphs achieving this bound.

AB - Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V - S is adjacent to a vertex in S and to a vertex in V - S. The restrained domination number of G, denoted by yr(G), is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then yr(U) ≥ d n 3 e, and provide a characterization of graphs achieving this bound.

KW - Restrained domination

KW - Unicyclic graph

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

U2 - 10.7151/dmgt.1433

DO - 10.7151/dmgt.1433

M3 - Article

AN - SCOPUS:77956520990

SN - 1234-3099

VL - 29

SP - 71

EP - 86

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

IS - 1

ER -

Restrained domination in unicyclic graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this