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, \(\gamma(P_{3}\square P_{n})=n+\lceil\frac{n}{4}\rceil\), \(\gamma(P_{4}\square P_{n})=n+\lceil\frac{2n}{3}\rceil\), γ(P 5□P n )=2n+1 and \(\gamma(P_{6}\square P_{n})=2n+\lceil\frac{n+2}{3}\rceil\).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Chang T, Clark E (1993) The domination numbers of the 5×n and 6×n grid graphs. J Graph Theory 17:81–107
Chang T, Clark E (1994) Domination numbers of complete grid graphs I. Ars Comb 38:97–111
Chartrand G, Lesniak L (2005) Graphs and digraphs, 4th edn. Chapman & Hall, Boca Raton
El-Zahar M, Pareek CM (1991) Domination number of products of graphs. Ars Combin 31:223–227
Faudree RJ, Schelp RH (1990) The domination number for the product of graphs. Congr Numer 79:29–33
Gravie S, Mollard M (1997) On domination numbers of Cartesian product of paths. Discrete Appl Math 80:247–250
Hare EO, Hedetniemi ST, Hare WR (1986) Algorithms for computing the domination number of k×n complete grid graphs. Congr Numer 55:81–92
Hartnell BL, Rall DF (2004) On dominating the Cartesian product of a graph and K 2. Discuss Math Graph Theory 24(3):389–402
Jacobson MS, Kinch LF (1983) On the domination number of products of graphs I. Ars Comb 18:33–44
Author information
Authors and Affiliations
Corresponding author
Additional information
This research is supported by NSFC (10671165), NSFC (10971255), the research fund for the doctoral program of Xinjiang Normal University (xjnubs0908), the Key Project of Chinese Ministry of Education (208161), Program for New Century Excellent Talents in University, and The Project-sponsored by SRF for ROCS, SEM.
Rights and permissions
About this article
Cite this article
Liu, J., Zhang, X. & Meng, J. On domination number of Cartesian product of directed paths. J Comb Optim 22, 651–662 (2011). https://doi.org/10.1007/s10878-010-9314-x
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-010-9314-x