Recognizing composite graphs is equivalent to testing graph isomorphism. (English) Zbl 0602.68033

We consider composition, a graph multiplication operator defined by Harary and Sabidussi, from a complexity theoretic point of view. If G and H are undirected graphs without self-loops, then the composite graph G[H] has vertex set V(G)\(\times V(H)\) and edge set \(\{(g_ 1,h_ 1)-(g_ 2,h_ 2):\) \(g_ 1-g_ 2\in E(G)\) or \(g_ 1=g_ 2\) and \(h_ 1-h_ 2\in E(H)\}\). We show that the complexity of testing whether an arbitrary graph can be written nontrivially as the composition of two smaller graphs is the same, to within polynomial factors, as the complexity of testing whether two graphs are isomorphic.


68Q25 Analysis of algorithms and problem complexity
05C99 Graph theory
Full Text: DOI