Download PDF - Highly connected counterexamples to a conjecture on α-dominationAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Highly connected counterexamples to a conjecture on α-domination

Authors 1, 2

Affiliations

  1. Computer and Automation Institute, Hungarian Academy of Sciences, H-1111 Budapest, Kende u. 13-17, Hungary
  2. Department of Computer Science, University of Veszprém, H-8200 Veszprém, Egyetem u. 10, Hungary

Abstract

An infinite class of counterexamples is given to a conjecture of Dahme et al. [1] concerning the minimum size of a dominating vertex set that contains at least a prescribed proportion of the neighbors of each vertex not belonging to the set.

Keywords

ENG
graph, dominating set, α-domination

Bibliography

  1. F. Dahme, D. Rautenbach and L. Volkmann, Some remarks on α-domination, Discuss. Math. Graph Theory 24 (2004) 423-430, doi: 10.7151/dmgt.1241.
  2. J.E. Dunbar, D.G, Hoffman, R.C. Laskar and L.R. Markus, α-domination, Discrete Math. 211 (2000) 11-26, doi: 10.1016/S0012-365X(99)00131-4.
  3. D.R. Woodall, Improper colourings of graphs, Pitman Res. Notes Math. Ser. 218 (1988) 45-63.
Discussiones Mathematicae Graph Theory
2005/25/3
Export to PBN, Opens in new tab
Pages:
435-440
Main language of publication
English
Received
2005-05-20
Published
2005

DOI: 10.7151/dmgt.1295

Exact and natural sciences