Abstract
A two-valued function f: V(D)→{−1, 1} defined on the vertices of a digraph D=(V(D), A(D)) is called a signed 2-independence function (S2IF) if f(N−[v])≤1 for every v in D. The weight of a S2IF is f(V(D))=∑v∈V(D)f(v). The maximum weight of a S2IF of D is the signed 2-independence number (or the lower against number) of D. Let Pm×Pn be the Cartesian product of directed paths Pm and Pn. In this paper, we determine the exact values of
for 1≤m≤5 and n≥1.
2010 AMS Subject Classification:
Acknowledgements
The authors thank anonymous referees for their careful reading, valuable comments and suggestions that helped to improve the presentation of the proofs.
Haichao Wang was supported in part by the Foundation for Distinguished Young Teachers, Shanghai Education Committee (no. sdl10023) and the Research Foundation of Shanghai University of Electric Power (no. K-2010-32). Hye Kyung Kim was supported in part by the Basic Science Research Program, the National Research Foundation of Korea, the Ministry of Education, Science and Technology (2011-0025989).