Feigenbaum, Joan; Schäffer, Alejandro A. Recognizing composite graphs is equivalent to testing graph isomorphism. (English) Zbl 0602.68033 SIAM J. Comput. 15, 619-627 (1986). 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. Cited in 6 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 05C99 Graph theory Keywords:graph products; graph composition; graph algorithms; graph multiplication operator; composite graph PDF BibTeX XML Cite \textit{J. Feigenbaum} and \textit{A. A. Schäffer}, SIAM J. Comput. 15, 619--627 (1986; Zbl 0602.68033) Full Text: DOI OpenURL