Algorithm to check the existence of H for a given G such that A (G) A (H) is graphical

A matrix with entries 0, 1 is graphical if it is symmetric and all its diagonal entries are zero. Let G1, G2 and G3 be graphs defined on the same set of vertices. The graph G3 is said to be the matrix product of graphs G1 and G2, if A(G1)A(G2) = A(G3), where A(Gi) is the adjacency matrix of the graph Gi, 1 ≤ i ≤ 3. In such a case, we say that G1 and G2 are companions of each other. The main purpose of this paper is to design an algorithm to check whether a given graph G has a companion. We derive conditions on n and m so that the generalized wheel graph, denoted by Wm,n, has a companion and also show that the mth power of the path graph Pn has no companion. Finally, we indicate a possible application of the algorithm in a problem of coloring of edges of the complete graph Kn.