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

asked 2022-07-15 04:51:31 +0100

licheng gravatar image

updated 2022-07-17 09:50:39 +0100

dan_fulea gravatar image

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.

https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_decompositions/graph_products.html

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

edit retag flag offensive close merge delete

Comments

1

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

David Coudert gravatar imageDavid Coudert ( 2022-07-15 10:13:54 +0100 )edit

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.

licheng gravatar imagelicheng ( 2022-07-15 13:04:46 +0100 )edit