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$.

Given two graphs, it is easy to obtain their lexicographic product. However the inverse process does not look so easy.

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

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

We know that there are already polynomial algorithms for the decomposition of the cartesian product of a graph. But for the lexicographic product, I don't know yet if there is some algorithm or code to implement the decomposition of the lexicographic products of a graph.

  • A polynomial time algorithm for finding the prime factors of Cartesian-product graphs", Discrete Applied Mathematics, 12 (2): 123–138, doi:10.1016/0166-218X(85)90066-6, MR 0808453
  • 1
    $\begingroup$ Feigenbaum, J.; Schäffer, A. A. (1986), "Recognizing composite graphs is equivalent to testing graph isomorphism", SIAM Journal on Computing, 15 (2): 619–627, doi:10.1137/0215045 $\endgroup$
    – John L.
    Jul 25, 2022 at 4:51
  • $\begingroup$ @JohnL. Sincere appreciation. I scanned the article quickly. It appears to imply a certain algorithm. $\endgroup$
    – licheng
    Jul 25, 2022 at 8:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.