Equality in a bound that relates the size and the restrained domination number of a graph

Johannes H. Hattingh; Ernst J. Joubert

doi:10.1007/s10878-015-9843-4

Equality in a bound that relates the size and the restrained domination number of a graph

Johannes H. Hattingh, Ernst J. Joubert

Mathematics and Applied Mathematics

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

1 Citation (Scopus)

Abstract

Let (Formula presented.) be a graph. A set (Formula presented.) is a restrained dominating set if every vertex in (Formula presented.) is adjacent to a vertex in (Formula presented.) and to a vertex in (Formula presented.). The restrained domination number of (Formula presented.) , denoted (Formula presented.) , is the smallest cardinality of a restrained dominating set of (Formula presented.). The best possible upper bound (Formula presented.) is established in Joubert (Discrete Appl Math 161:829–837, 2013) on the size (Formula presented.) of a graph (Formula presented.) with a given order (Formula presented.) and restrained domination number (Formula presented.). We extend this result to include the cases (Formula presented.) , and characterize graphs (Formula presented.) of order (Formula presented.) and restrained domination number (Formula presented.) for which (Formula presented.).

Original language	English
Pages (from-to)	1586-1608
Number of pages	23
Journal	Journal of Combinatorial Optimization
Volume	31
Issue number	4
DOIs	https://doi.org/10.1007/s10878-015-9843-4
Publication status	Published - 1 May 2016

Keywords

Domination
Graph
Order
Restrained domination
Size

ASJC Scopus subject areas

Computer Science Applications
Discrete Mathematics and Combinatorics
Control and Optimization
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1007/s10878-015-9843-4

Cite this

@article{da097fa9f99f49deafa5d86c512f6678,

title = "Equality in a bound that relates the size and the restrained domination number of a graph",

abstract = "Let (Formula presented.) be a graph. A set (Formula presented.) is a restrained dominating set if every vertex in (Formula presented.) is adjacent to a vertex in (Formula presented.) and to a vertex in (Formula presented.). The restrained domination number of (Formula presented.) , denoted (Formula presented.) , is the smallest cardinality of a restrained dominating set of (Formula presented.). The best possible upper bound (Formula presented.) is established in Joubert (Discrete Appl Math 161:829–837, 2013) on the size (Formula presented.) of a graph (Formula presented.) with a given order (Formula presented.) and restrained domination number (Formula presented.). We extend this result to include the cases (Formula presented.) , and characterize graphs (Formula presented.) of order (Formula presented.) and restrained domination number (Formula presented.) for which (Formula presented.).",

keywords = "Domination, Graph, Order, Restrained domination, Size",

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

note = "Publisher Copyright: {\textcopyright} 2015, Springer Science+Business Media New York.",

year = "2016",

month = may,

day = "1",

doi = "10.1007/s10878-015-9843-4",

language = "English",

volume = "31",

pages = "1586--1608",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "4",

}

TY - JOUR

T1 - Equality in a bound that relates the size and the restrained domination number of a graph

AU - Hattingh, Johannes H.

AU - Joubert, Ernst J.

PY - 2016/5/1

Y1 - 2016/5/1

N2 - Let (Formula presented.) be a graph. A set (Formula presented.) is a restrained dominating set if every vertex in (Formula presented.) is adjacent to a vertex in (Formula presented.) and to a vertex in (Formula presented.). The restrained domination number of (Formula presented.) , denoted (Formula presented.) , is the smallest cardinality of a restrained dominating set of (Formula presented.). The best possible upper bound (Formula presented.) is established in Joubert (Discrete Appl Math 161:829–837, 2013) on the size (Formula presented.) of a graph (Formula presented.) with a given order (Formula presented.) and restrained domination number (Formula presented.). We extend this result to include the cases (Formula presented.) , and characterize graphs (Formula presented.) of order (Formula presented.) and restrained domination number (Formula presented.) for which (Formula presented.).

AB - Let (Formula presented.) be a graph. A set (Formula presented.) is a restrained dominating set if every vertex in (Formula presented.) is adjacent to a vertex in (Formula presented.) and to a vertex in (Formula presented.). The restrained domination number of (Formula presented.) , denoted (Formula presented.) , is the smallest cardinality of a restrained dominating set of (Formula presented.). The best possible upper bound (Formula presented.) is established in Joubert (Discrete Appl Math 161:829–837, 2013) on the size (Formula presented.) of a graph (Formula presented.) with a given order (Formula presented.) and restrained domination number (Formula presented.). We extend this result to include the cases (Formula presented.) , and characterize graphs (Formula presented.) of order (Formula presented.) and restrained domination number (Formula presented.) for which (Formula presented.).

KW - Domination

KW - Graph

KW - Order

KW - Restrained domination

KW - Size

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

U2 - 10.1007/s10878-015-9843-4

DO - 10.1007/s10878-015-9843-4

M3 - Article

AN - SCOPUS:84923805836

SN - 1382-6905

VL - 31

SP - 1586

EP - 1608

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 4

ER -

Equality in a bound that relates the size and the restrained domination number of a graph

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this