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

Feigenbaum, Joan; Schäffer, Alejandro A.

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.

MSC:

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

Keywords:

graph products; graph composition; graph algorithms; graph multiplication operator; composite graph