Interference in Graphs

Abstract

Given a graph $I=(V,E),$ $\varnothing \ne D\subseteq V,$ and an arbitrary nonempty set $X,$ an injective function $f:V\to 2^X\setminus \{\varnothing \}$ is an interference of $D$ with respect to $I,$ if for every vertex $u\in V\setminus D$ there exists a neighbor $v\in D$ such that $f(u)\cap f(v)\ne \varnothing .$ 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\to 2^V$ (resp., $N_{L(G)}:E\to 2^E$) or its complementary function is an interference with respect to the complete graph $I=K_n.$

17 pp