# zbMATH — the first resource for mathematics

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)].

##### MSC:
 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:
##### References:
  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  F. Aurenhammer, J. Hagauer and W. Imrich, Factoring Cartesian-product graphs at logarithmic cost per edge, Comput. Complexity, to appear. · Zbl 0770.68064  Bandelt, H.-J., Retracts of hypercubes, J. graph theory, 8, 501-510, (1984) · Zbl 0551.05060  Coppersmith, D.; Feigenbaum, J., Finite graphs with two inequivalent factorizations under the composition operator, IBM research report RC 11149, (1985), Yorktown Heights  Dörfler, W.; Imrich, W., Über das starke produkt von endlichen graphen, Österreich. akad. wiss., Mathem.-natur. kl. S.-B. II, 178, 247-262, (1969) · Zbl 0194.56202  Dörfler, W.; Imrich, W., Das lexikographische produkt gerichteter graphen, Monats. math., 76, 21-30, (1972) · Zbl 0234.05109  T. Feder, Product graph representations, J. Graph Theory, to appear. · Zbl 0766.05092  Feigenbaum, J., Product graphs: some algorithmic and combinatorial results, Stanford university technical report STAN-CS-86-1121, Ph.D. thesis, (1986)  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  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  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  Hochstrasser, B., A note on Winkler’s algorithm for factoring a connected graph, Discrete math., 109, 127-132, (1992), (this Vol.) · Zbl 0780.05045  Imrich, W., Embedding graphs into Cartesian products, (), 266-274 · Zbl 0792.05044  Lovász, L., Operations with structures, Acta math. acad. sci. hung., 18, 321-328, (1967) · Zbl 0174.01401  Lovász, L., On the cancellation law among finite relational structures, Per. math. hung., 1, 145-156, (1971) · Zbl 0223.08002  McKenzie, R., Cardinal multiplication of structures with a reflexive relation, Fund. math., LXX, 59-101, (1971) · Zbl 0228.08002  Miller, D.J., The categorical product of graphs, Canad. J. math., XX, 1511-1521, (1968) · Zbl 0167.21902  Nes̆etr̆il, J., Representations of graphs by means of products and their complexity, (), 94-102  Sabidussi, G., Graph multiplication, Math. zeitschr., 72, 446-457, (1960) · Zbl 0093.37603  Tardif, C., Prefibers and the Cartesian products of metric spaces, Discrete math., 109, 283-288, (1992), (this Vol.) · Zbl 0777.05097  Vizing, V.G., The Cartesian product of graphs, Vycisl. sistemy, Comp. el. syst., 2, 352-365, (1966), English translation  Walker, J.W., Strict refinement for graphs and digraphs, J. combin. theory, 43, 140-150, (1987), Ser. B · Zbl 0587.05056  Weichsel, P.M., The Kronecker product of graphs, Proc. AMS, 13, 47-52, (1962) · Zbl 0102.38801  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.