Changing of the domination number of a graph: edge multisubdivision and edge removal

Author name not available (Why is that?)

Abstract: For a graphical property

m a t h c a l P

and a graph

G

, a subset

S

of vertices of

G

is a

m a t h c a l P

-set if the subgraph induced by

S

has the property

m a t h c a l P

. The domination number with respect to the property

m a t h c a l P

, denoted by

g a m m a_{m a t h c a l P} (G)

, is the minimum cardinality of a dominating

m a t h c a l P

-set. We define the domination multisubdivision number with respect to

m a t h c a l P

,denoted by

m s d_{m a t h c a l P} (G)

, as a minimum positive integer

k

such that there exists an edge which must be subdivided

k

times to change

g a m m a_{m} a t h c a l P (G)

. In this paper (a) we present necessary and sufficient conditions for a change of

g a m m a_{m a t h c a l P} (G)

after subdividing an edge of

G

once, (b) we prove that if

e

is an edge of a graph

G

then

g a m m a_{m} a t h c a l P (G_{e, 1}) < g a m m a_{m} a t h c a l P (G)

if and only if

g a m m a_{m} a t h c a l P (G - e) < g a m m a_{m} a t h c a l P (G)

(

G_{e, t}

denote the graph obtained from

G

by subdivision of

e

with

t

vertices), (c) we also prove that for every edge of a graph

G

is fulfilled

g a m m a_{m a t h c a l P} (G - e) l e q g a m m a_{m a t h c a l P} (G_{e, 3}) l e q g a m m a_{m a t h c a l P} (G - e) + 1

, and (d) we show that

m s d_{m a t h c a l P} (G) l e q 3

, where

m a t h c a l P

is hereditary and closed under union with

K_{1}

.

Recommendations

This page was built for publication: Changing of the domination number of a graph: edge multisubdivision and edge removal