Signed k-independence in digraphs

Abstract

Let k > 2 be an integer. A function / : V(D) {-1,1} defined on the vertex set V(D) of a digraph D is a signed k-independence function if ∑x∈N-[ν] f(x) < k; - 1 for each ν ∈ V(D), where N ^-[ν] consists of ν and all vertices of D from which arcs go into ν. The weight of a signed k-independence function / is defined by w(f) = f(V(D)). The maximum of weights w(f), taken over all signed k- independence functions / on D, is the signed k-independence number a^k _s(D) of D. In this work, we mainly present upper bounds on α^k_s(D), as for example α^k _s(D) < n - 2[δ^- +2-k] and α ^k_s(D)<δ⁺+2k-δ⁺-2/ δ⁺+δ⁺+2.n where n is the order, δ^- the maximum indegree and δ⁺ and δ⁺ are the maximum and minimum outdegree of the digraph D. Some of our results imply well-known properties on the signed 2-independence number of graphs and digraphs.