A note on signed cycle domination in graphs


Hossein Karami, Rana Khoeilar, Seyed Mahmoud Sheikholeslami




Let $G = (V, E)$ be a simple graph. A function $f : E \rightarrow\{-1, 1\}$ is said to be a signed cycle dominating function (SCDF) of $G$ if $um_{eı E(C)}f (e) \ge 1$ holds for every induced cycle $C$ of $G$. The signed cycle domination number of $G$ is defined as $\gamma_{sc}'(G) = \min\{um_{eı E(G)} f (e) \mid f \mbox{ is an } SCDF \mbox{ of } G\}$. B.\ Xu [4] conjectured that for any maximal planar graph $G$ of order $n \ge 3$, $\gamma_{sc}'(G) =n-2$. In this paper, we first prove that the conjecture is true and then we show that if $G$ is a connected cubic claw-free graph of order $n$, then $\gamma_{sc}'(G)\leq n$.