Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Decomposing Semi-complete Multigraphs and Directed Graphs into Paths of Length Two
verfasst von : Ajit A. Diwan, Sai Sandeep
Erschienen in: Algorithms and Discrete Applied Mathematics
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
Abstract
A \(P_3\)-decomposition of a graph is a partition of the edges of the graph into paths of length two. We give a simple necessary and sufficient condition for a semi-complete multigraph, that is a multigraph with at least one edge between each pair of vertices, to have a \(P_3\)-decomposition. We show that this condition can be tested in strongly polynomial-time, and that the same condition applies to a larger class of multigraphs. We give a similar condition for a \(P_3\)-decomposition of a semi-complete directed graph. In particular, we show that a tournament admits a \(P_3\)-decomposition iff its outdegree sequence is the degree sequence of a simple undirected graph.