PDF

Discussiones Mathematicae Graph Theory 25(3) (2005) 435-440
DOI: https://doi.org/10.7151/dmgt.1295

HIGHLY CONNECTED COUNTEREXAMPLES TO A CONJECTURE ON α-DOMINATION

Zsolt Tuza

Computer and Automation Institute
Hungarian Academy of Sciences
H-1111 Budapest, Kende u. 13-17, Hungary
and
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: graph, dominating set, α-domination.

2000 Mathematics Subject Classification: 05C69, 05C35.

References

[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.

Received 20 May 2005