Article ID Journal Published Year Pages File Type
4648520 Discrete Mathematics 2012 7 Pages PDF
Abstract

Let DD be a finite and simple digraph with vertex set V(D)V(D), and let f:V(D)→{−1,1}f:V(D)→{−1,1} be a two-valued function. If ∑x∈N−[v]f(x)≤1∑x∈N−[v]f(x)≤1 for each v∈V(D)v∈V(D), where N−[v]N−[v] consists of vv and all vertices of DD from which arcs go into vv, then ff is a signed 2-independence function on DD. The sum f(V(D))f(V(D)) is called the weight w(f)w(f) of ff. The maximum of weights w(f)w(f), taken over all signed 2-independence functions ff on DD, is the signed 2-independence number αs2(D) of DD.In this work, we mainly present upper bounds on αs2(D), as for example αs2(D)≤n−2⌈Δ−/2⌉ and αs2(D)≤Δ++1−2⌈δ−2⌉Δ++1⋅n, where nn is the order, Δ−Δ− and δ−δ− are the maximum and the minimum indegree and Δ+Δ+ is the maximum outdegree of the digraph DD. Some of our theorems imply well-known results on the signed 2-independence number of graphs.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,