2017/07/17 by Danial Dervovic, Dervovic, Danial, Simone Severini +1 · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.1707.05179
Algorithm 1 (IvBE) is irreparably flawed. Moreover, Theorem 2, concerning perfection of weak modular products of balanced, bipartite graphs is incorrect. Thank you to an anonymous reviewer for pointing out these flaws in the paper. We have now enumerated all perfect product graphs in the work at arXiv:1809.09939
openalex publication_date 2017/07/17 · arxiv created 2018/09/27 · arxiv updated 2018/09/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A 1978 theorem of Kozen states that two graphs on n vertices are isomorphic if and only if there is a clique of size n in the weak modular product between the two graphs. Restricting to bipartite graphs and considering complete bipartite subgraphs (bicliques) therein, we study the combinatorics of the weak modular product. We identify cases where isomorphism is tractable using this approach, which we call Isomorphism via Biclique Enumeration (IvBE). We find that IvBE is polynomial for bipartite 2K2-free graphs and quasi-polynomial for families of bipartite graphs, where the largest induced matching and largest induced crown graph grows slowly in n, that is, O(polylog n). Furthermore, as expected a straightforward corollary of Kozen's theorem and Lovász's sandwich theorem is if the weak modular product between two graphs is perfect, then checking if the graphs are isomorphic is polynomial in n. However, we show that for balanced, bipartite graphs this is only true in a few trivial cases. In doing so we define a new graph product on bipartite graphs, the very weak modular product. The results pertaining to bicliques in bipartite graphs proved here may be of independent interest.