Recognizing Composite Graphs is Equivalent to Testing Graph Isomorphism

DOI10.1137/0215045zbMath0602.68033OpenAlexW1969797470WikidataQ29398669 ScholiaQ29398669MaRDI QIDQ3738557

Joan Feigenbaum, Alejandro A. Schäffer

Publication date: 1986

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0215045

zbMATH Keywords

graph algorithmscomposite graphgraph productsgraph compositiongraph multiplication operator

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (05C99)

Related Items (6)

Bounds for metric dimension and defensive $k$-alliance of graphs under deleted lexicographic product ⋮ Unnamed Item ⋮ Equipartitions of graphs ⋮ Finding the prime factors of strong direct product graphs in polynomial time ⋮ Direct product primality testing of graphs is GI-hard ⋮ A polynomial time algorithm for finding the prime factors of Cartesian- product graphs

This page was built for publication: Recognizing Composite Graphs is Equivalent to Testing Graph Isomorphism