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.
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 following code.
from sage.graphs.graph_decompositions.graph_products import is_cartesian_product
g = graphs.PetersenGraph()
is_cartesian_product(g)
False
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. [https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_decompositions/graph_products.html]
Similarly, is there any codes for the lexicographic product decomposition of graphs.