An upper bound for the restrained domination number of a graph with minimum degree at least two in terms of order and minimum degree

Johannes H. Hattingh; Ernst J. Joubert

doi:10.1016/j.dam.2009.03.010

An upper bound for the restrained domination number of a graph with minimum degree at least two in terms of order and minimum degree

Johannes H. Hattingh, Ernst J. Joubert

Mathematics and Applied Mathematics

Georgia State University

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

9 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. We will show that if G is a connected graph of order n and minimum degree δ and not isomorphic to one of nine exceptional graphs, then γ_r (G) ≤ frac(n - δ + 1, 2).

Original language	English
Pages (from-to)	2846-2858
Number of pages	13
Journal	Discrete Applied Mathematics
Volume	157
Issue number	13
DOIs	https://doi.org/10.1016/j.dam.2009.03.010
Publication status	Published - 6 Jul 2009

Keywords

Domination
Graph
Minimum degree
Order of a graph
Restrained domination
Upper bound

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2009.03.010

Cite this

@article{c46a686e18a746a392ea75bfc899c944,

title = "An upper bound for the restrained domination number of a graph with minimum degree at least two in terms of order and minimum degree",

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. We will show that if G is a connected graph of order n and minimum degree δ and not isomorphic to one of nine exceptional graphs, then γr (G) ≤ frac(n - δ + 1, 2).",

keywords = "Domination, Graph, Minimum degree, Order of a graph, Restrained domination, Upper bound",

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

year = "2009",

month = jul,

day = "6",

doi = "10.1016/j.dam.2009.03.010",

language = "English",

volume = "157",

pages = "2846--2858",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "13",

}

TY - JOUR

T1 - An upper bound for the restrained domination number of a graph with minimum degree at least two in terms of order and minimum degree

AU - Hattingh, Johannes H.

AU - Joubert, Ernst J.

PY - 2009/7/6

Y1 - 2009/7/6

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. We will show that if G is a connected graph of order n and minimum degree δ and not isomorphic to one of nine exceptional graphs, then γr (G) ≤ frac(n - δ + 1, 2).

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. We will show that if G is a connected graph of order n and minimum degree δ and not isomorphic to one of nine exceptional graphs, then γr (G) ≤ frac(n - δ + 1, 2).

KW - Domination

KW - Graph

KW - Minimum degree

KW - Order of a graph

KW - Restrained domination

KW - Upper bound

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

U2 - 10.1016/j.dam.2009.03.010

DO - 10.1016/j.dam.2009.03.010

M3 - Article

AN - SCOPUS:67349194969

SN - 0166-218X

VL - 157

SP - 2846

EP - 2858

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 13

ER -

An upper bound for the restrained domination number of a graph with minimum degree at least two in terms of order and minimum degree

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this