Domination in colored complete graphs

descriptionPublicationkeyboard_double_arrow_right Article 01 Dec 1989 English Publisher:WileyJournal:Journal of Graph Theory, volume 13, pages 713-718 (issn: 0364-9024, eissn: 1097-0118,

Copyright policy )

Authors: Paul Erdös; Ralph J. Faudree; András Gyárfás; Richard H. Schelp;

doi: 10.1002/jgt.3190130607

Domination in colored complete graphs

- Summary
- Subjects
- Metrics

Abstract

AbstractWe prove the following conjecture of Erdös and Hajnal: For any fixed positive integer t and for any 2‐coloring of the edges of kn, there exists X ⊂ v(KN) such that |≦| and X monochromatically dominates all but at most n/2t vertices of Kn. In fact, X can be constructed by a fast greedy algorithm.

Related Organizations

University of Memphis
United States

Keywords

Graph theory, Graph theory (including graph drawing) in computer science, dominating set, r-domination

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	8
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average