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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alspach, B.: The Oberwolfach problem. In: The CRC Handbook of Combinatorial Designs, pp. 394–395. CRC Press, Boca Raton (1996)
Brys, K., Lonc, Z.: Polynomial cases of graph decomposition: a complete solution of Holyers problem. Discrete Math. 309, 1294–1326 (2009)
Diwan, A.A.: \({P_3}\)-decomposition of directed graphs. Discrete Appl. Math. (to appear). http://dx.doi.org/10.1016/j.dam.2016.01.039
Dor, D., Tarsi, M.: Graph decomposition is NP-complete: a complete proof of Holyers conjecture. SIAM J. Comput. 26, 1166–1187 (1997)
Edmonds, J.: Maximum matching and a polyhedron with 0,1-vertices. J. Res. Natl. Bureau Stan. Sect. B 69, 125–130 (1965)
Gyarfas, A., Lehel, J.: Packing trees of different order into \(K_n\). In: Combinatorics (Proceedings of Fifth Hungarian Colloquium, Keszthely, 1976), vols. I, 18, Colloquium Mathematical Society, Janos Bolyai, pp. 463–469. North-Holland, Amsterdam (1978)
Fulkerson, D.J., Hoffman, A.J., McAndrew, M.H.: Some properties of graphs with multiple edges. Can. J. Math. 17, 166–177 (1965)
King, V., Rao, S., Tarjan, R.: A faster deterministic maximum flow algorithm. J. Algorithms 17(3), 447–474 (1994)
Kotzig, A.: From the theory of finite regular graphs of degree three and four. Casopis. Pest. Mat. 82, 76–92 (1957)
Kouider, M., Maheo, M., Brys, K., Lonc, Z.: Decomposition of multigraphs. Discuss. Math. Graph Theor. 18, 225–232 (1998)
Ringel, G.: Problem 25. In: Theory of Graphs and its Applications, Proceedings of International Symposium Smolenice 1963 Nakl, CSAV, Praha, p. 162 (1964)
Tutte, W.T.: The factorisation of linear graphs. J. Lond. Math. Soc. 22, 107–111 (1947)
Wilson, R.M.: Decompositions of complete graphs into subgraphs isomorphic to a given graph. In: Proceedings of British Combinatorial Conference, pp. 647–659 (1975)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Diwan, A.A., Sandeep, S. (2017). Decomposing Semi-complete Multigraphs and Directed Graphs into Paths of Length Two. In: Gaur, D., Narayanaswamy, N. (eds) Algorithms and Discrete Applied Mathematics. CALDAM 2017. Lecture Notes in Computer Science(), vol 10156. Springer, Cham. https://doi.org/10.1007/978-3-319-53007-9_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-53007-9_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-53006-2
Online ISBN: 978-3-319-53007-9
eBook Packages: Computer ScienceComputer Science (R0)