Partial Star Products: A Local Covering Approach for the Recognition of Approximate Cartesian Product Graphs

Abstract

This paper is concerned with the recognition of approximate graph products with respect to the Cartesian product. Most graphs are prime, although they can have a rich product-like structure. The proposed algorithms are based on a local approach that covers a graph by small subgraphs, so-called partial star products, and then utilizes this information to derive the global factors and an embedding of the graph under investigation into Cartesian product graphs.

References in corpus (1)

• Square Property, Equitable Partitions, and Product-like Graphs

Cited by in corpus (2)

• On the Cartesian Skeleton and the Factorization of the Strong Product of Digraphs
• Square Property, Equitable Partitions, and Product-like Graphs