On defensive alliances and line graphs

Abstract: Let

G a m m a

be a simple graph of size

m

and degree sequence

d e l t a_{1} g e d e l t a_{2} g e ... g e d e l t a_{n}

. Let

c a l L (G a m m a)

denotes the line graph of

G a m m a

. The aim of this paper is to study mathematical properties of the alliance number,

a (c a l L (G a m m a)

, and the global alliance number,

g a m m a_{a} (c a l L (G a m m a))

, of the line graph of a simple graph. We show that

l c e i l f r a c d e l t a_{n} + d e l t a_{n - 1} - 1 2 c e i l l e a (c a l L (G a m m a)) l e d e l t a_{1} .

In particular, if

G a m m a

is a

d e l t a

-regular graph (

d e l t a > 0

), then

a (c a l L (G a m m a)) = d e l t a

, and if

G a m m a

is a

(d e l t a_{1}, d e l t a_{2})

-semiregular bipartite graph, then

a (c a l L (G a m m a)) = l c e i l f r a c d e l t a_{1} + d e l t a_{2} - 1 2 c e i l

. As a consequence of the study we compare

a (c a l L (G a m m a))

and

a (G a m m a)

, and we characterize the graphs having

a (c a l L (G a m m a)) < 4

. Moreover, we show that the global-connected alliance number of

c a l L (G a m m a)

is bounded by

g a m m a_{c a} (c a l L (G a m m a)) g e l c e i l s q r t D (G a m m a) + m - 1 - 1 c e i l,

where

D (G a m m a)

denotes the diameter of

G a m m a

, and we show that the global alliance number of

c a l L (G a m m a)

is bounded by

g a m m a_{a} (c a l L (G a m m a)) g e q l c e i l f r a c 2 m d e l t a_{1} + d e l t a_{2} + 1 c e i l

. The case of strong alliances is studied by analogy.

Recommendations

Cites work

Cited in

(33)

This page was built for publication: On defensive alliances and line graphs