On the X-join decomposition for undirected graphs

In his paper [17], Sabidussi defined the X-join of a family of graphs. Cowan, James, Stanton gave in [6] and O(n⁴) algorithm that decomposes a graph, when possible, into the X-join of the family of its subgraphs. We give here another approach using an equivalence relation on the edge set of the graph. We prove that if G and its complement are connected then there exists an unique class of edges that covers all the vertices of G. This theorem yields immediately an O(n³) decomposition algorithm.