Signed 2-independence of Cartesian product of directed paths

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 P_m×P_n be the Cartesian product of directed paths P_m and P_n. In this paper, we determine the exact values of for 1≤m≤5 and n≥1.

Keywords:

• signed 2-independence function
• signed 2-independence number
• Cartesian product
• indegree
• directed path

2010 AMS Subject Classification:

• 05C69

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).