ArticleOriginal scientific text

Title

Quasiperfect domination in triangular lattices

Authors 1

Affiliations

  1. University of Puerto Rico, Rio Piedras, PR 00931-3355

Abstract

A vertex subset S of a graph G is a perfect (resp. quasiperfect) dominating set in G if each vertex v of G∖S is adjacent to only one vertex (dv ∈ {1,2} vertices) of S. Perfect and quasiperfect dominating sets in the regular tessellation graph of Schläfli symbol {3,6} and in its toroidal quotients are investigated, yielding the classification of their perfect dominating sets and most of their quasiperfect dominating sets S with induced components of the form Kν, where ν ∈ {1,2,3} depends only on S.

Keywords

perfect dominating set, quasiperfect dominating set, triangular lattice

Bibliography

  1. D.W. Bange, A.E. Barkauskas and P.J. Slater, Efficient dominating sets in graphs, Appl. Discrete Math, eds. R.D. Ringeisen and F.S. Roberts (SIAM, Philadelphia, 1988) 189-199.
  2. I.J. Dejter, Perfect domination of regular grid graphs, Australasian J. Combin. 92 (2008) 99-114.
  3. I.J. Dejter and A.A. Delgado, Perfect dominating sets in grid graphs, JCMCC 70 (2009), to appear.
  4. L. Fejes Tóth, Regular Figures (Pergamon Press, Oxford UK, 1964).
  5. J. Kratochvil and M. Krivánek, On the Computational Complexity of Codes in Graphs, in: Proc. MFCS 1988, LNCS 324 (Springer-Verlag), 396-404.
  6. C. Thomassen, On the Nelson unit distance coloring problem, Amer. Math. Monthly 106 (1999) 850-853, doi: 10.2307/2589618.
Pages:
179-198
Main language of publication
English
Published
2009
Exact and natural sciences