Graphs with large disjunctive total domination number

Authors Michael A. Henning, Viroshan Naicker

Publication date 30 April 2015

Full work available at URL https://arxiv.org/abs/1409.1681, https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2727/0.html

zbMATH Keywords

disjunctive total dominating set total dominating set

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: Let

G

be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number,

g a m m a_{t} (G)

. A set

S

of vertices in

G

is a disjunctive total dominating set of

G

if every vertex is adjacent to a vertex of

S

or has at least two vertices in

S

at distance

2

from it. The disjunctive total domination number,

g a m m a_{t}^{d} (G)

, is the minimum cardinality of such a set. We observe that

g a m m a_{t}^{d} (G) l e g a m m a_{t} (G)

. Let

G

be a connected graph on

n

vertices with minimum degree

d e l t a

. It is known [J. Graph Theory 35 (2000), 21--45] that if

d e l t a g e 2

and

n g e 11

, then

g a m m a_{t} (G) l e 4 n / 7

. Further [J. Graph Theory 46 (2004), 207--210] if

d e l t a g e 3

, then

g a m m a_{t} (G) l e n / 2

. We prove that if

d e l t a g e 2

and

n g e 8

, then

g a m m a_{t}^{d} (G) l e n / 2

and we characterize the extremal graphs.

Recommendations

Cited in

(17)

This page was built for publication: Graphs with large disjunctive total domination number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5249240)