Factoring cartesian‐product graphs

DOI10.1002/jgt.3190180604zbMath0811.05054OpenAlexW2009742209MaRDI QIDQ4309984

Wilfried Imrich, Janez Žerovnik

Publication date: 18 April 1995

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.3190180604

zbMATH Keywords

distancesconvex hullCartesian productprime graphsequivalence relationprime factorization

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Graph theory (05C99)

Related Items

Algorithm for recognizing Cartesian graph bundles, Estimation of Laplacian spectra of direct and strong product graphs, The Cartesian product of hypergraphs, Recognizing Cartesian graph bundles, Partial cubes and their \(\tau\)-graphs, Unique square property, equitable partitions, and product-like graphs, Unnamed Item, Structure of Fibonacci cubes: a survey, An algorithm forK-convex closure and an application, Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs, A local prime factor decomposition algorithm, The grid property and product-like hypergraphs

Cites Work

• Unnamed Item
• Factoring a graph in polynomial time
• Computing equivalence classes among the edges of a graph with applications
• A note on Winkler's algorithm for factoring a connected graph
• Graph multiplication
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Über das schwache Kartesische Produkt von Graphen
• On Isometric Embeddings of Graphs
• Product graph representations
• Weak cartesian product of graphs