On domination number of Cartesian product of directed paths

On domination number of Cartesian product of directed paths

0.00 Avg rating—0 Votes
Article ID: iaor201111132
Volume: 22
Issue: 4
Start Page Number: 651
End Page Number: 662
Publication Date: Nov 2011
Journal: Journal of Combinatorial Optimization
Authors: , ,
Keywords: heuristics
Abstract:

Let γ(G) denote the domination number of a digraph G and let P m □P n denote the Cartesian product of P m and P n , the directed paths of length m and n. In this paper, we give a lower and upper bound for γ(P m □P n ). Furthermore, we obtain a necessary and sufficient condition for P m □P n to have efficient dominating set, and determine the exact values: γ(P 2□P n )=n, γ ( P 3 □ P n ) = n + ⌈ n 4 ⌉ equ1 , γ ( P 4 □ P n ) = n + ⌈ 2 n 3 ⌉ equ2 , γ(P 5□P n )=2n+1 and γ ( P 6 □ P n ) = 2 n + ⌈ n + 2 3 ⌉ equ3 .

Reviews

Required fields are marked *. Your email address will not be published.