Finding the prime factors of strong direct product graphs in polynomial time. (English) Zbl 0786.68076

Finite undirected connected graphs are studied. It is known that, if a graph \(G\) is decomposed as the strong direct product of some graphs – denoted as \(G=G_ 1 \boxtimes G_ 2 \boxtimes \cdots \boxtimes G_ k\) – and the \(G_ i\)’s are irreducible as for the strong direct product, then the \(G_ i\)’s are uniquely determined apart from isomorphy [see W. Dörfler, and W. Imrich, Österreich. Akad. Wiss., Math.-Naturw. Kl., S.-Ber., Abt. II. 178, 247-262 (1970; Zbl 0194.562), and R. McKenzie, Fundamenta Math. 70, 59-101 (1971; Zbl 0228.08002)]. This fact does not imply the unambiguous labeling of a vertex \(v\) of \(G\) in the form \((v_ 1,v_ 2,\dots,v_ k)\); in addition, if \(v,w\) are adjacent vertices of \(G\), then the number of equalities \(v_ i=w_ i\) – from among the \(k\) possible ones – is not uniquely determined.
The authors give an algorithm such that it determines the irreducible strong direct factors of a given graph \(G\). The time demand of this algorithm depends polynomially on the number of vertices of \(G\). In the first stage of the method, \(G\) is decomposed into the form \(G=H \boxtimes K_ 1 \boxtimes K_ 2 \boxtimes \dots \boxtimes K_ s\) where any \(K_ j\) is a complete graph with a prime number of vertices and maximal \(s\). Henceforth \(H\) is analyzed. A lot of effort is devoted for surmounting the ambiguity features mentioned above. It is utilized that the analogous decomposition task with respect to the Cartesian product of graphs can be executed in polynomial time [see J. Feigenbaum, J. Hershberger and A. A. Schäffer, Discrete Appl. Math. 12, 123-138 (1985; Zbl 0579.68028), and P. Winkler, Eur. J. Comb. 8, 209-212 (1987; Zbl 0625.05050)].


68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI


[1] Aurenhammer, F.; Hagauer, J., Computing equivalence classes among the edges of a graph with applications, Discrete Math., 109, 3-12 (1992), (this Vol.) · Zbl 0795.05130
[3] Bandelt, H.-J., Retracts of hypercubes, J. Graph Theory, 8, 501-510 (1984) · Zbl 0551.05060
[4] Coppersmith, D.; Feigenbaum, J., Finite graphs with two inequivalent factorizations under the composition operator, IBM Research Report RC 11149 (1985), Yorktown Heights
[5] Dörfler, W.; Imrich, W., Über das starke Produkt von endlichen Graphen, Österreich. Akad. Wiss.. Österreich. Akad. Wiss., Mathem.-Natur. Kl. S.-B. II, 178, 247-262 (1969) · Zbl 0194.56202
[6] Dörfler, W.; Imrich, W., Das lexikographische Produkt gerichteter Graphen, Monats. Math., 76, 21-30 (1972) · Zbl 0234.05109
[8] Feigenbaum, J., Product graphs: some algorithmic and combinatorial results, Stanford University Technical Report STAN-CS-86-1121. Stanford University Technical Report STAN-CS-86-1121, Ph.D. Thesis (1986)
[9] Feigenbaum, J., Directed graphs have unique Cartesian factorizations that can be found in polynomial time, Discrete Appl. Math., 15, 105-110 (1986) · Zbl 0637.05018
[10] Feigenbaum, J.; Hershberger, J.; Schäffer, A. A., A polynomial time algorithm for finding the prime factors of Cartesian-product graphs, Discrete Appl. Math., 12, 123-138 (1985) · Zbl 0579.68028
[11] Feigenbaum, J.; Schäffer, A. A., Recognizing composite graphs is equivalent to testing graph isomorphism, SIAM J. Comp., 15, 619-627 (1986) · Zbl 0602.68033
[12] Hochstrasser, B., A note on Winkler’s algorithm for factoring a connected graph, Discrete Math., 109, 127-132 (1992), (this Vol.) · Zbl 0780.05045
[13] Imrich, W., Embedding graphs into Cartesian products, (Graph Theory and its Applications: East and West. Graph Theory and its Applications: East and West, Ann. N.Y. Acad. of Sciences, 576 (1989)), 266-274 · Zbl 0792.05044
[14] Lovász, L., Operations with structures, Acta Math. Acad. Sci. Hung., 18, 321-328 (1967) · Zbl 0174.01401
[15] Lovász, L., On the cancellation law among finite relational structures, Per. Math. Hung., 1, 145-156 (1971) · Zbl 0223.08002
[16] McKenzie, R., Cardinal multiplication of structures with a reflexive relation, Fund. Math., LXX, 59-101 (1971) · Zbl 0228.08002
[17] Miller, D. J., The categorical product of graphs, Canad. J. Math., XX, 1511-1521 (1968) · Zbl 0167.21902
[18] Nes̆etr̆il, J., Representations of graphs by means of products and their complexity, (Gruska, J.; Chytil, M., Proceedings, 10th Annual Symposium on Mathematical Foundations of Computer Science, S̆trbské Pleso, Czechoslovakia. Proceedings, 10th Annual Symposium on Mathematical Foundations of Computer Science, S̆trbské Pleso, Czechoslovakia, Lecture Notes in Computer Science, 118 (1981), Springer: Springer Berlin), 94-102
[19] Sabidussi, G., Graph multiplication, Math. Zeitschr., 72, 446-457 (1960) · Zbl 0093.37603
[20] Tardif, C., Prefibers and the Cartesian products of metric spaces, Discrete Math., 109, 283-288 (1992), (this Vol.) · Zbl 0777.05097
[21] Vizing, V. G., The Cartesian product of graphs, Vycisl. Sistemy. Vycisl. Sistemy, Comp. El. Syst., 2, 352-365 (1966), English translation
[22] Walker, J. W., Strict refinement for graphs and digraphs, J. Combin. Theory, 43, 140-150 (1987), Ser. B · Zbl 0587.05056
[23] Weichsel, P. M., The Kronecker product of graphs, Proc. AMS, 13, 47-52 (1962) · Zbl 0102.38801
[24] Winkler, P., Factoring a graph in polynomial time, European J. Combin., 8, 209-212 (1987) · Zbl 0625.05050
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.