Disjunctive domination in graphs with minimum degree at least two

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Abstract: A set

D

of vertices in

G

is a disjunctive dominating set in

G

if every vertex not in

D

is adjacent to a vertex of

D

or has at least two vertices in

D

at distance

2

from it in

G

. The disjunctive domination number,

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

, of

G

is the minimum cardinality of a disjunctive dominating set in

G

. In this paper, we show that if

G

be a graph of order at least

3

,

d e l t a (G) g e q 2

and with no component isomorphic to any of eight forbidden graphs, then

g a m m a_{2}^{d} (G) l e q f r a c | G | 3

. Moreover, we provide an infinite family of graphs attaining this bound. In addition, we also study the case that

G

is a claw-free graph with minimum degree at least two.

Review text

From the author's abstract: ``A set \(D\) of vertices in a graph \(G\) is called a disjunctive dominating set in \(G\) if every vertex not in \(D\) is adjacent to a vertex in \(D\) or has at least two vertices in \(D\) at distance \(2\) from it in \(G\). The disjunctive domination number, denoted \(\gamma^d_2(G)\), of \(G\) is the minimum cardinality of a disjunctive dominating set in \(G\). In this paper, the author proves that if \(G\) is a graph of order \(n \geq3\) with \(\delta(G) \geq 2\) such that no component in \(G\) is isomorphic to any of eight specific graphs given in the paper, then \(\gamma^d_2(G) \leq \frac{n}{3}\). The author also provides an infinite family of graphs that attain the upper bound of \(\frac{n}{3}\).

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Disjunctive domination in graphs with minimum degree at least two

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