Factoring a graph in polynomial time. (English) Zbl 0625.05050

The Cartesian product \(G\times H\) of graphs G and H has vertices (g,h) where g is a vertex in G and h a vertex in H. Two vertices of \(G\times H\), say \((g_ 1,h_ 1)\) and \((g_ 2,h_ 2)\), are connected by an edge in \(G\times H\), just when either \(\{g_ 1,g_ 2\}\) is an edge of G and \(h_ 1=h_ 2\), or when \(g_ 1=g_ 2\) and \(\{h_ 1,h_ 2\}\) is an edge of H. It was proved by G. Sabidussi [Math. Z. 72, 446-457 (1960; Zbl 0093.376)] that Cartesian product admits unique factorization. The author proves that there is a polynomial time algorithm for constructing the prime factorization of a given connected graph. The same result, using completely different techniques, was proved also in [J. Feigenbaum, J. Hershberger and A. A. Schaffer, Discrete Appl. Math. 12, 123-138 (1985; Zbl 0579.68028)].
Reviewer: G.Slutzki


05C99 Graph theory
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI


[1] J. Feigenbaum, J. Hershberger, A. Schaffer, A polynomial time algorithm for finding the prime factors of Cartesian-product graphs, Disc. Appl. Math. 12 (2), 123-138. · Zbl 0579.68028
[2] R.L. Graham, P.M. Winkler, On isometric embeddings of graphs, Trans. Amer. Math. Soc. 288 (2), 527-536. · Zbl 0576.05017
[3] Imrich, W., ()
[4] Sabidussi, G., Graph multiplication, Math. zeitschr., 72, 446-457, (1960) · Zbl 0093.37603
[5] Welsh, D., Problems in computational complexity, (), 75-85
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.