On the Domination Number of Cartesian Product of Two Directed Cycles
Denote by γ(G) the domination number of a digraph G and Cm□Cn the Cartesian product of Cm and Cn, the directed cycles of length m,n≥2. In 2010, Liu et al. determined the exact values of γ(Cm□Cn) for m=2,3,4,5,6. In 2013, Mollard determined the exact values of γ(Cm□Cn) for m=3k+2. In this paper, we g...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2013-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2013/619695 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Denote by γ(G) the domination number of a digraph G and Cm□Cn the Cartesian product of Cm and Cn, the directed cycles of length m,n≥2. In 2010, Liu et al. determined the exact values of γ(Cm□Cn) for m=2,3,4,5,6. In 2013, Mollard determined the exact values of γ(Cm□Cn) for m=3k+2. In this paper, we give lower and upper bounds of γ(Cm□Cn) with m=3k+1 for different cases. In particular, ⌈2k+1n/2⌉≤γ(C3k+1□Cn)≤⌊2k+1n/2⌋+k. Based on the established result, the exact values of γ(Cm□Cn) are determined for m=7 and 10 by the combination of the dynamic algorithm, and an upper bound for γ(C13□Cn) is provided. |
|---|---|
| ISSN: | 1110-757X 1687-0042 |