Upper Bounds on Signed $2$-Independence Number of Graphs

Abstract

A function $f:V\to \{-1,1\}$ defined on the vertices of a graph $G=(V,E)$ is a signed $2$-independence function if the sum of its function values over any closed neighbourhood is at most one. That is, for every $v\in V$, $f(N[v])\le 1$, where $N[v]$ consists of $v$ and every vertex adjacent to $v$. The weight of a signed $2$-independence function is $f(V)=\sum f(v)$. The signed $2$-independence number of a graph $G$, denoted ${\alpha }_s^2(G)$, is the maximum weight of a signed $2$-independence function of $G$. In this article, we give some new upper bounds on ${\alpha }_s^2(G)$ of $G$, and establish a sharp upper bound on ${\alpha }_s^2(G)$ for an $r$-partite graph.