# Is there code to identify a decomposition of the lexicographic product of a graph?

In graph theory, the lexicographic product or (graph) composition G ∙ H of graphs G and H is a graph such that

- the vertex set of G ∙ H is the cartesian product V(G) × V(H); and
- any two vertices (u,v) and (x,y) are adjacent in G ∙ H if and only if either u is adjacent with x in G or u = x and v is adjacent with y in H.

Here's what I thought about.

**Recognition problem**: Given a graph G, can we guess whether there exist graphs G_1,...,G_k such that G=G_1 ∙ ⋯ ∙G_k ?

For the **Cartesian product** of graphs, this problem can be solved by the funtion `is_cartesian_product`

.

```
from sage.graphs.graph_decompositions.graph_products import is_cartesian_product
g = graphs.PetersenGraph()
is_cartesian_product(g)
> False
```

and

```
g = graphs.Grid2dGraph(5,5)
g.relabel()
b,D = g.is_cartesian_product(g, relabeling=True)
b
D
> True
{0: (0, 20),
1: (0, 15),
2: (0, 10),
3: (0, 5),
4: (0, 0),
5: (1, 20),
6: (1, 15),
7: (1, 10),
8: (1, 5),
9: (1, 0),
10: (2, 20),
11: (2, 15),
12: (2, 10),
13: (2, 5),
14: (2, 0),
15: (3, 20),
16: (3, 15),
17: (3, 10),
18: (3, 5),
19: (3, 0),
20: (4, 20),
21: (4, 15),
22: (4, 10),
23: (4, 5),
24: (4, 0)}
```

For the above codes, we refer to the links below.

Similarly, is there any code for the lexicographic product decomposition of graphs.

We don't have such code yet. Feel free to contribute.

I read the book "Handbook of product graphs", that says that the recognition complexity of lexicographic products is polynomially equivalent to the graph isomorphism problem. But I don't see the corresponding algorithm.