The product of the restrained domination numbers of a graph and its complement

Johannes H. Hattingh; Ernst J. Joubert

doi:10.1007/s10114-014-2492-1

The product of the restrained domination numbers of a graph and its complement

Johannes H. Hattingh, Ernst J. Joubert

Mathematics and Applied Mathematics

East Carolina University

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

3 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 γ _r(G), is the smallest cardinality of a restrained dominating set of G. In this paper, we show that if G is a graph of order n ≥ 4, then γ_r(G)γ_r(Ḡ} ≤ 2n. We also characterize the graphs achieving the upper bound.

Original language	English
Pages (from-to)	445-452
Number of pages	8
Journal	Acta Mathematica Sinica, English Series
Volume	30
Issue number	3
DOIs	https://doi.org/10.1007/s10114-014-2492-1
Publication status	Published - Mar 2014

Keywords

Graph
Nordhaus-Gaddum
domination
restrained domination
upper bound

ASJC Scopus subject areas

General Mathematics
Applied Mathematics

Access to Document

10.1007/s10114-014-2492-1

Cite this

@article{cb13409744444d59ab649a0d183cbff9,

title = "The product of the restrained domination numbers of a graph and its complement",

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 γ r(G), is the smallest cardinality of a restrained dominating set of G. In this paper, we show that if G is a graph of order n ≥ 4, then γr(G)γr(Ḡ} ≤ 2n. We also characterize the graphs achieving the upper bound.",

keywords = "Graph, Nordhaus-Gaddum, domination, restrained domination, upper bound",

author = "Hattingh, {Johannes H.} and Joubert, {Ernst J.}",

year = "2014",

month = mar,

doi = "10.1007/s10114-014-2492-1",

language = "English",

volume = "30",

pages = "445--452",

journal = "Acta Mathematica Sinica, English Series",

issn = "1439-8516",

publisher = "Springer Verlag",

number = "3",

}

TY - JOUR

T1 - The product of the restrained domination numbers of a graph and its complement

AU - Hattingh, Johannes H.

AU - Joubert, Ernst J.

PY - 2014/3

Y1 - 2014/3

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 γ r(G), is the smallest cardinality of a restrained dominating set of G. In this paper, we show that if G is a graph of order n ≥ 4, then γr(G)γr(Ḡ} ≤ 2n. We also characterize the graphs achieving the upper 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 γ r(G), is the smallest cardinality of a restrained dominating set of G. In this paper, we show that if G is a graph of order n ≥ 4, then γr(G)γr(Ḡ} ≤ 2n. We also characterize the graphs achieving the upper bound.

KW - Graph

KW - Nordhaus-Gaddum

KW - domination

KW - restrained domination

KW - upper bound

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

U2 - 10.1007/s10114-014-2492-1

DO - 10.1007/s10114-014-2492-1

M3 - Article

AN - SCOPUS:84893596252

SN - 1439-8516

VL - 30

SP - 445

EP - 452

JO - Acta Mathematica Sinica, English Series

JF - Acta Mathematica Sinica, English Series

IS - 3

ER -

The product of the restrained domination numbers of a graph and its complement

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this