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 at 4:51
  • $\begingroup$ @JohnL. Sincere appreciation. I scanned the article quickly. It appears to imply a certain algorithm. $\endgroup$
    – licheng
    Jul 25 at 8:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.