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!
|
| _version_ | 1832562195606536192 |
|---|---|
| author | Zehui Shao Enqiang Zhu Fangnian Lang |
| author_facet | Zehui Shao Enqiang Zhu Fangnian Lang |
| author_sort | Zehui Shao |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-7eef2c44a2dd4062b53038b174fb71cf |
| institution | Kabale University |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2013-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-7eef2c44a2dd4062b53038b174fb71cf2025-02-03T01:23:17ZengWileyJournal of Applied Mathematics1110-757X1687-00422013-01-01201310.1155/2013/619695619695On the Domination Number of Cartesian Product of Two Directed CyclesZehui Shao0Enqiang Zhu1Fangnian Lang2School of Information Science and Technology, Chengdu University, Chengdu 610106, ChinaSchool of Electronic Engineering and Computer Science, Peking University, Beijing 100871, ChinaSchool of Information Science and Technology, Chengdu University, Chengdu 610106, ChinaDenote 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.http://dx.doi.org/10.1155/2013/619695 |
| spellingShingle | Zehui Shao Enqiang Zhu Fangnian Lang On the Domination Number of Cartesian Product of Two Directed Cycles Journal of Applied Mathematics |
| title | On the Domination Number of Cartesian Product of Two Directed Cycles |
| title_full | On the Domination Number of Cartesian Product of Two Directed Cycles |
| title_fullStr | On the Domination Number of Cartesian Product of Two Directed Cycles |
| title_full_unstemmed | On the Domination Number of Cartesian Product of Two Directed Cycles |
| title_short | On the Domination Number of Cartesian Product of Two Directed Cycles |
| title_sort | on the domination number of cartesian product of two directed cycles |
| url | http://dx.doi.org/10.1155/2013/619695 |
| work_keys_str_mv | AT zehuishao onthedominationnumberofcartesianproductoftwodirectedcycles AT enqiangzhu onthedominationnumberofcartesianproductoftwodirectedcycles AT fangnianlang onthedominationnumberofcartesianproductoftwodirectedcycles |