The Cartesian product of graphs with loops

DOI10.26493/1855-3974.715.C3DMaRDI QIDQ2835387zbMATH OpenOpenAlexWikidataFDO

Authors Tetiana Boiko, Johannes Cuno, Wilfried Imrich, Florian Lehner, Christiaan E. van de Woestijne

Publication date 2 December 2016

Published in Ars Mathematica Contemporanea (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.6887

zbMATH Keywords

algorithmsfactorizationsmonoids

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76) Graph algorithms (graph-theoretic aspects) (05C85) Divisibility and factorizations in commutative rings (13A05) Arithmetic theory of semigroups (20M13)

Abstract: We extend the definition of the Cartesian product to graphs with loops and show that the Sabidussi-Vizing unique 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 this factorization can be computed in O(m) time, where m is the number of edges of the given graph.

Recommendations

• Cartesian products of directed graphs with loops
• Factoring a graph in polynomial time
• Unique prime Cartesian factorization of graphs over finite fields
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• On Cartesian skeletons of graphs

Cited in

(5)

• Cartesian products of graphs and metric spaces
• Cartesian products of directed graphs with loops
• Asymmetric colorings of products of graphs and digraphs
• Note on decompositions based on the vertex-removing synchronised graph product
• Monoid algebras and graph products

This page was built for publication: The Cartesian product of graphs with loops

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835387)