Interference in graphs

Abstract: Given a graph

I = (V, E),

e m p t y s e t e D s u b s e t e q V,

and an arbitrary nonempty set

X,

an injective function

f : V o 2^{X} s e t m i n u s e m p t y s e t

is an interference of

D

with respect to

I,

if for every vertex

u i n V s e t m i n u s D

there exists a neighbor

v i n D

such that

f (u) c a p f (v) e e m p t y s e t .

We initiate a study of interference in graphs. We study special cases of the difficult problem of finding a smallest possible set

X,

and we decide when, given a graph

G = (V, E (G))

(resp., its line graph

L (G)

) the open neighborhood function

N_{G} : V o 2^{V}

(resp.,

N_{L (G)} : E o 2^{E}

) or its complementary function is an interference with respect to the complete graph

I = K_{n} .

Recommendations

Cited in

(3)

This page was built for publication: Interference in graphs