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.