IJPAM: Volume 109, No. 7 (2016)

Title

A CLASS OF PERFECT DOMINATION
PROBLEMS ON DIAMOND LATTICES

Authors

Paul Manuel$^1$, D. Antony Xavier$^2$, S. Kulandai Therese$^3$, Andrew Arokiaraj$^2$
$^1$Department of Information Science
Kuwait University
Safat,13060, KUWAIT
$^2$Department of Mathematics
Loyola College
Chennai, 600034, INDIA
$^3$Department of Mathematics
St. Mary's College
Thoothukudi, 628001, INDIA

Abstract

A set $S$ of vertices in a graph $G$ is said to be a perfect $k$-dominating set if every vertex in $V-S$ is adjacent to exactly $k$ vertices of $S$. The perfect $k$-domination number, $\gamma_{kp}(G)$ is the minimum cardinality of a perfect $k$-dominating set of $G$. In this paper, we construct a minimum perfect $k$-dominating set where $k=1,2,3,4$ for infinite diamond lattice.

History

Received: October 1, 2016
Revised:
Published: February 20, 2017

AMS Classification, Key Words

AMS Subject Classification: 05C69
Key Words and Phrases: dominating set, $k$-dominating set, perfect dominating set, perfect $k$-dominating set, infinite diamond lattice

Download Section

Download paper from here.
You will need Adobe Acrobat reader. For more information and free download of the reader, see the Adobe Acrobat website.

Bibliography

1
B. Chaluvaraju, M. Chellali and K. A. Vidya, Perfect $k$-domination in graphs, Australasian Journal of Combinatorics, 48 (2010), 175-184.

2
B. Chaluvaraju and K. A. Vidya, Bounds on perfect $k$-domination in trees: An algorithmic approach, Opuscula Mathematica , 32(4) (2012), 707-714.

3
G.J. Chang, Algorithmic aspects of domination in graphs, Handbook of Combinatorial Optimization, D.-Z. Du and P.M. Pardalos (Eds.) 3 (1998), 339-405.

4
E.J. Cockayne, B.L. Hartnell, S.T. Hedetniemi, R. Laskar, Perfect domination in graphs, Journal of Combinatorics, Information and System Sciences, 18 (1993), 136-148.

5
I.J. Dejter, Perfect domination in regular grid graphs, Australian Journal of Combinatorics, 42 (2008), 99-114.

6
J. F. Fink and M. S. Jacobson, Graph theory with applications to algorithms and computer science, John Wiley and Sons, Inc., New York, NY, USA, (1985), 283-300.

7
H. Hatami and P. Hatami, Perfect Dominating Sets in the Cartesian Products of Prime Cycles, The Electronic Journal of Combinatorics, 14(1) (2007).

8
M.S. Jacobson and K. Peters, Complexity questions for $n$-domination and related parameters, Congr. Numer. Eighteenth Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, MB, 1988) 68 (1989), 7-22.

9
A. Khodkar and S.M. Sheikholeslami, On perfect double dominating sets in grids, cylinders and tori, Australasian Journal of Combinatorics, 37, (2007), 131-139.

10
J. Lee, Independent perfect domination sets in Cayley graphs, Journal of Graph Theory, 37 (4) (2001), 213-219.

11
M. Livingston and Q. F. Stout, Perfect Dominating Sets , Congressus Numerantium, 79 (1990), 187-203.

12
P. Manuel and M. Guizani, Broadcasting algorithms of carbon nanotubes, Journal of Computational and Theoretical Nanoscience, 8 (2011), 1-9.

13
C. Martinez, R.Beivide , J.Gutierrez and E. Gabidulin, On the perfect t-dominating set problem in circulant graphs and codes over Gaussian integers , Proceedings of International Symposium on Information Theory (ISIT 2005) , 2005.

14
C. Martinez, C. Camarero and R. Beivide, Perfect graph codes over two dimensional lattices, IEEE International Symposium on Information Theory (ISIT), (2010).

15
P.M. Weichsel, Dominating sets in n-cubes, Journal of Graph Theory , 18(5) (1994), 479-488.

16
D.V. Wieren, M. Livingston and Q.F. Stout, Perfect Dominating Sets on Cube-Connected Cycles, Congressus Numerantium, 97 (1993), 51-70.

How to Cite?

DOI: 10.12732/ijpam.v109i7.15 How to cite this paper?

Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2016
Volume: 109
Issue: 7
Pages: 115 - 123


Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).