Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Nash-Williams-type and Chvátal-type Conditions in One-Conflict Graphs
verfasst von : Christian Laforest, Benjamin Momège
Erschienen in: SOFSEM 2015: Theory and Practice of Computer Science
Verlag: Springer Berlin Heidelberg
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
Nash-Williams and Chvátal conditions (1969 and 1972) are well known and classical sufficient conditions for a graph to contain a Hamiltonian cycle. In this paper, we add constraints, called
conflicts
. A conflict is a pair of edges of the graph that cannot be both in a same Hamiltonian path or cycle. Given a graph
G
and a set of conflicts, we try to determine whether
G
contains such a Hamiltonian path or cycle without conflict. We focus in this paper on graphs in which each vertex is part of at most one conflict, called
one-conflict graphs
. We propose Nash-Williams-type and Chvátal-type results in this context.