Highly connected counterexamples to a conjecture on α-domination

• Autorzy: Zsolt Tuza
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

graph; dominating set; α-domination

Kategorie tematyczne

• 05C35: Extremal problems
• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2005
• Tom: 25
• Numer: 3
• Strony: 435-440

Daty

wydano

2005

otrzymano

2005-05-20

Twórcy

autor

Zsolt Tuza

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

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1295