Factoring Cartesian-product graphs. (English) Zbl 0811.05054

The authors consider the structure of the equivalence relation \(\sigma\) on the edge set of a graph \(G\) belonging to the decomposition of \(G\) into a Cartesian product of prime graphs; this prime factorization theory was founded by G. Sabidussi [Math. Z. 72, 446-457 (1960; Zbl 0093.376)]. For a family of graphs \((G_ \iota)_{\iota \in I}\), the Cartesian product \(\Gamma = \square_{\iota \in I} G_ \iota\) is the graph \(\Gamma = (V(\Gamma), E(\Gamma))\) with \(V(\Gamma) := \{(x_ \iota)_{\iota \in I} : x_ \iota \in V(G_ \iota)\), \(\iota \in I\}\) and \(E(\Gamma) := \bigcup_{\kappa \in I} E_ \kappa\), where \(E_ \kappa := \{\{(x_ \iota), (y_ \iota)\} : (x_ \iota), (y_ \iota) \in V(\Gamma) \wedge \{x_ \kappa, y_ \kappa\} \in E(G_ \kappa) \wedge \forall \iota (\iota \in I - \{\kappa\} \to x_ \iota = y_ \iota)\}\), \(\kappa \in I\); for any \(a = (a_ \iota) \in V(\Gamma)\), the connected component \(G\) of \(\Gamma\) containing \(a\) is called the weak Cartesian product \(G = \square^ a_{\iota \in I} G_ \iota\). The decomposition \(E(G) = \bigcup_{\kappa \in I}(E_ \kappa \cap E(G))\) determines an equivalence relation \(\sigma(\square^ a G_ \iota)\) on \(E(G)\) belonging to this weak Cartesian product. For any connected graph \(G\), it is defined (a) \(e, f \in E(G)\) are in the relation \(\delta\) iff either \(e\) and \(f\) are adjacent and there is no chordless square containing \(e\) and \(f\) or \(e = f\) or \(e\) and \(f\) are opposite edges of a chordless square; (b) \(e = \{x, y\} \in E(G)\) and \(f = \{x', y'\} \in E(G)\) are in (Djoković’s) relation \(\Theta\) iff the distances satisfy \(d(x,x') + d(y,y') \neq d(x,y') + d(x', y)\); (c) a subgraph \(H\) of \(G\) is convex (in \(G\)) iff every shortest \(G\)-path between any two vertices of \(H\) is in \(H\); (d) an equivalence relation \(\gamma\) on \(E(G)\) with the equivalence classes \(E_ \iota\), \(\iota \in I\), is convex iff for any \(K \subseteq I\) every connected component of the subgraph induced on \(\bigcup_{\iota \in K} E_ \iota\) is convex; (e) \(e = \{x, z\} \in E(G)\) and \(f = \{z, y\} \in E(G)\) are in the relation \(\tau\) iff \(z\) is the unique common neighbour of \(x\) and \(y\). Obviously, for any weak Cartesian product representation \(\square^ a _{\iota \in I} G_ \iota\) of \(G\) the relation \(\sigma(\square^ a G_ \iota)\) is convex and contains the transitive closure \(\delta^*\) of \(\delta\).
Now, the following main results are proved for any (finite or infinite) connected graph \(G\): (1) Every convex equivalence relation \(\gamma \supseteq \delta\) on \(E(G)\) induces a representation of \(G\) as a weak Cartesian product. (2) The intersection of an arbitrary set of convex equivalence relations on \(E(G)\) containing \(\delta\) is convex. Thus there is a finest convex equivalence relation on \(E(G)\) containing \(\delta\), the convex hull \(C(\delta)\) of \(\delta\). (3) From (1) and (2) it follows a new proof of the known statement that \(G\) has a unique representation as a weak Cartesian product of prime graphs (prime factorization). (4) The equivalence relation \(\sigma\) on \(E(G)\) belonging to this prime factorization is \(\sigma = C(\delta)\). (5) \(\sigma = (\delta \cup \Theta)^*\); moreover, every convex equivalence relation \(\gamma \supseteq \tau\) on \(E(G)\) contains \(\delta\), and \(\sigma = (\tau \cup \Theta)^* = C(\tau)\).


05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C99 Graph theory
05C12 Distance in graphs


Zbl 0093.376
Full Text: DOI


[1] Aurenhammer, Cartesian Graph Factorization Comput, Complexity 2 pp 331– (1992)
[2] Aurenhammer, Computing equivalence classes among the edges of a graph with applications, Discrete Math. 109 pp 3– (1992) · Zbl 0795.05130
[3] Feder, Product graph representations, J. Graph Theory. 16 pp 467– (1993) · Zbl 0766.05092
[4] Feigenbaum, A polynomial time algorithm for finding the prime factors of Cartesian-product graphs, Discrete Appl. Math. 12 pp 123– (1985) · Zbl 0579.68028
[5] Graham, On isometric embeddings of graphs, Trans. Am. Math. Soc. 288 pp 527– (1985) · Zbl 0576.05017
[6] Hochstrasser, A note on Winkler’s algorithm for factoring a connected graph, Discrete Math. 109 pp 127– (1992) · Zbl 0780.05045
[7] Imrich, Über das schwache Kartesische Produkt von Graphen, J. Combinat. Theory Ser. B 11 pp 1– (1971) · Zbl 0218.05069
[8] Imrich, Embedding graphs into cartesian products, Ann. NY Acad. Sci. 576 pp 266– (1989) · Zbl 0792.05044
[9] Miller, Weak Cartesian product of graphs, Colloq. Math. 21 pp 55– (1970) · Zbl 0195.54301
[10] Sabidussi, Graph multiplication, Math. Z. 72 pp 446– (1960) · Zbl 0093.37603
[11] C. Tardif Prefibres in Cartesian product of metric spaces University of Montreal
[12] Vizing, The Cartesian product of graphs [in Russian]., Vyčisl. Syst. 9 pp 30– (1963)
[13] Comp. El. Syst. 2 1966 352 365
[14] Winkler, Factoring a graph in polynomial time, Eur. J. Combinat. 8 pp 209– (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.