Speaker
Wilfried Imrich
(Montanuniversitaet Leoben)
Description
We extend the definition of the Cartesian product to graphs with loops and show that the Sabidussi-Vizing unique prime factorization theorem for connected finite simple graphs still holds in this context for all connected finite graphs with at least one unlooped vertex.
We also prove that the prime factorization can be computed in O(m) time, where m is the size of the given graph.
Joint work with Tetiana Boiko (TU Graz), Johannes Cuno (TU Graz), Florian Lehner (TU Graz), and Christiaan E. van de Woestijne (MU Leoben)
Primary author
Wilfried Imrich
(Montanuniversitaet Leoben)
Co-author
Marcin Wardynski
(Montanuniversitaet Leoben)
