Anzeige
Erschienen in:
1995 | ReviewPaper | Buchkapitel
On domination elimination orderings and domination graphs
Extended abstract
verfasst von : Elias Dahihaus, Peter Hammer, Frédéric Maffray, Stephan Olariu
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Several efficient algorithms have been proposed to construct a perfect elimination ordering of the vertices of a chordal graph. We study a generalization of perfect elimination orderings, so called domination elimination orderings (deo). We show that graphs with the property that each induced subgraph has a deo (domination graphs) are related to formulas that can be reduced to formulas with a very simple structure. We also show that every brittle graph and every graph with no induced house and no chordless cycle of length at least five (HC-free graphs) are domination graphs. Moreover, every ordering produced by the Maximum Cardinality Search Procedure on an HC-free graph is a deo.