Signed total 2-independence in digraphs

Abstract

Let D be a finite and simple digraph with vertex set V(D), and let f: V(D) → { - 1, 1} be a two-valued function. If Σ_xϵN-(v) f(x) ≤ 1 for each v ϵ V(D), where N^-(v) consists of all vertices of D from which arcs go into v, then f is a signed total 2-independence function on D. The sum f(V(D)) is called the weight w(f) of f. The maximum of weights w(f), taken over all signed total 2-independence functions f on D, is the signed total 2-independence number α²_st(D) of D. In this work, we mainly present upper bounds on α²_st(D), as for example α²_st(D) ≤ n - 2[Δ^-/2], where n is the order and Δ^- is the maximum indegree of the digraph D. Some of our results imply well-known bounds on the signed total 2-independence number of graphs. In addition, we derive some Nordhaus-Gaddum type inequalities.