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]) \leq 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^2_s(G)\), is the maximum weight of a signed \(2\)-independence function of \(G\). In this article, we give some new upper bounds on \(\alpha^2_s(G)\) of \(G\), and establish a sharp upper bound on \(\alpha^2_s(G)\) for an \(r\)-partite graph.