Finding the prime factors of strong direct product graphs in polynomial time (Q686286): Difference between revisions

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 \textit{W. Dörfler}, and \textit{W. Imrich}, Österreich. Akad. Wiss., Math.-Naturw. Kl., S.-Ber., Abt. II. 178, 247-262 (1970; Zbl 0194.562), and \textit{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 \textit{J. Feigenbaum}, \textit{J. Hershberger} and \textit{A. A. Schäffer}, Discrete Appl. Math. 12, 123-138 (1985; Zbl 0579.68028), and \textit{P. Winkler}, Eur. J. Comb. 8, 209-212 (1987; Zbl 0625.05050)].