Cartesian products of directed graphs with loops

DOI10.1016/J.DISC.2018.01.021MaRDI QIDQ1709534zbMATH OpenOpenAlexFDO

Authors Wilfried Imrich, Iztok Peterin

Publication date 5 April 2018

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

prime graphsCartesian productinfinite graphsweak Cartesian productdirected graph with loops

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Infinite graphs (05C63) Graph operations (line graphs, products, etc.) (05C76)

Abstract: We show that every nontrivial finite or infinite connected directed graph with loops and at least one vertex without a loop is uniquely representable as a Cartesian or weak Cartesian product of prime graphs. For finite graphs the factorization can be computed in linear time and space.

Recommendations

• The Cartesian product of graphs with loops
• scientific article; zbMATH DE number 739124
• PRODUCTS OF CIRCULANT GRAPHS
• Nonmedian direct products of graphs with loops.
• Boundary vertices of Cartesian product of directed graphs
• On linkedness in the Cartesian product of graphs
• scientific article; zbMATH DE number 2075761
• Cartesian products of block graphs
• scientific article; zbMATH DE number 3954951

Cites work

• scientific article; zbMATH DE number 3308993 (Why is no real title available?)
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time
• Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time
• Graph multiplication
• Handbook of product graphs
• Recognizing Cartesian products in linear time
• The Cartesian product of graphs with loops
• Weak cartesian product of graphs
• Über das schwache Kartesische Produkt von Graphen

Cited in

(6)

• scientific article; zbMATH DE number 3893233 (Why is no real title available?)
• The Cartesian product of graphs with loops
• Product graph representations
• A note on interaction between groups and convergence spaces
• Direct product of automorphism groups of digraphs
• Factoring cartesian‐product graphs

This page was built for publication: Cartesian products of directed graphs with loops

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