On domination number and distance in graphs

Abstract: A vertex set

S

of a graph

G

is a emph{dominating set} if each vertex of

G

either belongs to

S

or is adjacent to a vertex in

S

. The emph{domination number}

g a m m a (G)

of

G

is the minimum cardinality of

S

as

S

varies over all dominating sets of

G

. It is known that

g a m m a (G) g e f r a c 13 (d i a m (G) + 1)

, where

d i a m (G)

denotes the diameter of

G

. Define

C_{r}

as the largest constant such that

g a m m a (G) g e C_{r} s u m_{1 l e i < j l e r} d (x_{i}, x_{j})

for any

r

vertices of an arbitrary connected graph

G

; then

C_{2} = f r a c 13

in this view. The main result of this paper is that

C_{r} = f r a c 1 r (r - 1)

for

r g e q 3

. It immediately follows that

g a m m a (G) g e q m u (G) = f r a c 1 n (n - 1) W (G)

, where

m u (G)

and

W (G)

are respectively the average distance and the Wiener index of

G

of order

n

. As an application of our main result, we prove a conjecture of DeLaVi~{n}a et al.;that

g a m m a (G) g e q f r a c 12 (e c c_{G} (B) + 1)

, where

e c c_{G} (B)

denotes the eccentricity of the boundary of an arbitrary connected graph

G

.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: On domination number and distance in graphs