Vertices contained in all or in no minimum disjunctive dominating set of a tree

Michael A. Henning; Sinclair A. Marcon

Vertices contained in all or in no minimum disjunctive dominating set of a tree

Michael A. Henning, Sinclair A. Marcon

Mathematics and Applied Mathematics

University of Johannesburg

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

2 Citations (Scopus)

Abstract

A dominating set in a graph G is a set S of vertices of G such that every vertex not in S is adjacent to a vertex of S. The domination number, γ(G), of G is the cardinality of a minimum dominating set of G. A set S of vertices in G is a disjunctive dominating set in G if every vertex not in S is adjacent to a vertex of S or has at least two vertices in S at distance 2 from it in G. The disjunctive domination number, γ^d ₂(G), of G is the cardinality of a minimum disjunctive dominating set in G. In this paper, we characterize the vertices contained in all or in no minimum disjunctive dominating set of a tree.

Original language	English
Pages (from-to)	95-123
Number of pages	29
Journal	Utilitas Mathematica
Volume	105
Publication status	Published - Nov 2017

Keywords

Disjunctive domination
Domination
Trees.

ASJC Scopus subject areas

Statistics and Probability
Statistics, Probability and Uncertainty
Applied Mathematics

Cite this

@article{e06ab88e7bf84b4eb057943158e1c5e2,

title = "Vertices contained in all or in no minimum disjunctive dominating set of a tree",

abstract = "A dominating set in a graph G is a set S of vertices of G such that every vertex not in S is adjacent to a vertex of S. The domination number, γ(G), of G is the cardinality of a minimum dominating set of G. A set S of vertices in G is a disjunctive dominating set in G if every vertex not in S is adjacent to a vertex of S or has at least two vertices in S at distance 2 from it in G. The disjunctive domination number, γd 2(G), of G is the cardinality of a minimum disjunctive dominating set in G. In this paper, we characterize the vertices contained in all or in no minimum disjunctive dominating set of a tree.",

keywords = "Disjunctive domination, Domination, Trees.",

author = "Henning, \{Michael A.\} and Marcon, \{Sinclair A.\}",

year = "2017",

month = nov,

language = "English",

volume = "105",

pages = "95--123",

journal = "Utilitas Mathematica",

issn = "0315-3681",

publisher = "Utilitas Mathematica Publishing Inc.",

}

TY - JOUR

T1 - Vertices contained in all or in no minimum disjunctive dominating set of a tree

AU - Henning, Michael A.

AU - Marcon, Sinclair A.

PY - 2017/11

Y1 - 2017/11

N2 - A dominating set in a graph G is a set S of vertices of G such that every vertex not in S is adjacent to a vertex of S. The domination number, γ(G), of G is the cardinality of a minimum dominating set of G. A set S of vertices in G is a disjunctive dominating set in G if every vertex not in S is adjacent to a vertex of S or has at least two vertices in S at distance 2 from it in G. The disjunctive domination number, γd 2(G), of G is the cardinality of a minimum disjunctive dominating set in G. In this paper, we characterize the vertices contained in all or in no minimum disjunctive dominating set of a tree.

AB - A dominating set in a graph G is a set S of vertices of G such that every vertex not in S is adjacent to a vertex of S. The domination number, γ(G), of G is the cardinality of a minimum dominating set of G. A set S of vertices in G is a disjunctive dominating set in G if every vertex not in S is adjacent to a vertex of S or has at least two vertices in S at distance 2 from it in G. The disjunctive domination number, γd 2(G), of G is the cardinality of a minimum disjunctive dominating set in G. In this paper, we characterize the vertices contained in all or in no minimum disjunctive dominating set of a tree.

KW - Disjunctive domination

KW - Domination

KW - Trees.

UR - https://www.scopus.com/pages/publications/85052851012

M3 - Article

AN - SCOPUS:85052851012

SN - 0315-3681

VL - 105

SP - 95

EP - 123

JO - Utilitas Mathematica

JF - Utilitas Mathematica

ER -

Vertices contained in all or in no minimum disjunctive dominating set of a tree

Abstract

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this