FROM IRREDUNDANCE TO ANNIHILATION: A BRIEF OVERVIEW OF SOME DOMINATION PARAMETERS OF GRAPHS

Resumen

Durante los últimos treinta años, el concepto de dominación en grafos ha levantado un interés impresionante. Una bibliografía reciente sobre el tópico contiene más de 1200 referencias y el número de definiciones nuevas está creciendo continuamente. En vez de intentar dar un catálogo de todas ellas, examinamos las nociones más clásicas e importantes (tales como dominación independiente, dominación irredundante, k-cubrimientos, conjuntos k-dominantes, conjuntos Vecindad Perfecta, ...) y algunos de los resultados más

significativos.

PALABRAS CLAVES: Teoría de grafos, Dominación.

ABSTRACT

During the last thirty years, the concept of domination in graphs has generated an impressive interest. A recent bibliography on the subject contains more than 1200 references and the number of new definitions is continually increasing. Rather than trying to give a catalogue of all of them, we survey the most classical and important notions (as independent domination, irredundant domination, k-coverings, k-dominating sets, Perfect Neighborhood sets, ...) and some of the most significant results.

KEY WORDS: Graph theory, Domination.