The inverse problem of a mathematical question is often very interesting.

I'm glad to see that Maple 2023 has added several new graph operations. The GraphTheory[ConormalProduct], GraphTheory[LexicographicProduct], GraphTheory[ModularProduct] and GraphTheory[StrongProduct] commands were introduced in Maple 2023.

In fact, we often encounter their inverse problems in graph theory as well. Fortunately, most of them can find corresponding algorithms, but the implementation of these algorithms is almost nonexistent.

I once asked a question involving the inverse operation of the lexicographic product.

• https://www.mapleprimes.com/questions/235863-An-Inverse-Problem-Of-Lexicographic

Today, I will introduce the inverse operation of line graph operations. (In fact, I am trying to approach these problems with a unified perspective.)

To obtain the line graph of a graph is easy, but what about the reverse? That is to say, to test whether the graph is a line graph. Moreover, if a graph  g is the line graph of some other graph h, can we find h? (Maybe not unique. **Whitney isomorphism theorem tells us that if the line graphs of two connected graphs are isomorphic, then the underlying graphs are isomorphic, except in the case of the triangle graph K_3 and the claw K_{1,3}, which have isomorphic line graphs but are not themselves isomorphic.)

Wikipedia tells us that there are two approaches, one of which is to check if the graph contains any of the nine forbidden induced subgraphs. 

Beineke's forbidden-subgraph characterization:  A graph is a line graph if and only if it does not contain one of these nine graphs as an induced subgraph.

This approach can always be implemented, but it may not be very fast. Another approach is to use the linear time algorithms mentioned in the following article. 

• Roussopoulos, N. D. (1973), "A max {m,n} algorithm for determining the graph H from its line graph G", Information Processing Letters, 2 (4): 108–112, doi:10.1016/0020-0190(73)90029-X, MR 0424435

Or: 

•   Lehot, Philippe G. H. (1974), "An optimal algorithm to detect a line graph and output its root graph", Journal of the ACM, 21 (4): 569–575, doi:10.1145/321850.321853, MR 0347690, S2CID 15036484.

SageMath can do that: 

   root_graph()

Return the root graph corresponding to the given graph.

    is_line_graph()

Check whether a graph is a line graph.

For example, K_{2,2,2,2} is not the line graph of any graph.

K2222 = graphs.CompleteMultipartiteGraph([2, 2, 2, 2])
C=K2222.is_line_graph(certificate=True)[1]
C.show() # Containing the ninth forbidden induced subgraph.

Another Sage example for showing that the complement of the Petersen graph is the line graph of K_5.

P = graphs.PetersenGraph()
C = P.complement()
sage.graphs.line_graph.root_graph(C, verbose=False)

(Graph on 5 vertices, {0: (0, 1), 1: (2, 3), 2: (0, 4), 3: (1, 3), 4: (2, 4), 5: (3, 4), 6: (1, 4), 7: (1, 2), 8: (0, 2), 9: (0, 3)})

Following this line of thought, can Maple gradually implement the inverse operations of some standard graph operations? 

Here are some examples:

•   CartesianProduct
•   TensorProduct
•   ConormalProduct
•   LexicographicProduct
•   ModularProduct
•   StrongProduct
•   LineGraph
•  GraphPower