ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 11 (2016) 1-9
The Cartesian product of graphs with loops
Tetiana Boiko *
Institut für Mathematische Strukturtheorie, Technische Universität Graz Steyrergasse 30/III, 8010 Graz, Austria
Johannes Cuno *
Institut fur Mathematische Strukturtheorie, Technische Universitat Graz Steyrergasse 30/III, 8010 Graz, Austria
Wilfried Imrich *
Department Mathematik und Informationstechnologie Montanuniversitat Leoben, Franz-Josef-Straße 18, 8700 Leoben, Austria
Florian Lehner *
Institut fur Geometrie, Technische Universitat Graz Kopernikusgasse 24/IV, 8010 Graz, Austria
Christiaan E. van de Woestijne f
Department Mathematik und Informationstechnologie Montanuniversitat Leoben, Franz-Josef-Straße 18, 8700 Leoben, Austria
Received 27 August 2014, accepted 30 October 2014, published online 6 July 2015
We extend the definition of the Cartesian product to graphs with loops and show that the Sabidussi-Vizing unique factorization theorem for connected finite simple graphs still holds in this context for all connected finite graphs with at least one unlooped vertex. We also prove that this factorization can be computed in O(m) time, where m is the number of edges of the given graph.
Keywords: Graphs, monoids, factorizations, algorithms. Math. Subj. Class.: 05C70, 13A05, 20M13, 05C85.
* Tetiana Boiko, Johannes Cuno, Wilfried Imrich, and Florian Lehner are supported by the Austrian Science Fund (FWF): W1230, Doctoral Program "Discrete Mathematics."
t Christiaan E. van de Woestijne is supported by the Austrian Science Fund (FWF): S9611. This project is part of the Austrian National Research Network "Analytic Combinatorics and Probabilistic Number Theory."
E-mail ¡addresses: boiko@math.tugraz.at (Tetiana Boiko), cuno@math.tugraz.at (Johannes Cuno), imrich@unileoben.ac.at (Wilfried Imrich), f.lehner@tugraz.at (Florian Lehner), c.vandewoestijne@unileoben.ac.at (Christiaan E. van de Woestijne)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
2
Ars Math. Contemp. 11 (2016) 35-47
1 Introduction
This paper considers finite undirected graphs that may contain loops, or, put differently, symmetric binary relations on finite sets. One may define several binary operations on such graphs; these are explored in the recently revised monograph [1]. The well-known Cartesian product of finite undirected graphs is usually defined only for simple graphs, that is, for graphs that do not contain multiple edges between the same pair of vertices and, more importantly for us, do not contain loops. Here we extend this definition.
Before doing so, let us fix the notation. For us, a graph G = (V, E) will always be a finite undirected graph without multiple edges. The edge set E is taken to be a set of ordered pairs of vertices; thus, a loop on the vertex v e V corresponds to the edge (v, v) e E, and as all graphs are undirected, we have (v, w) e E if and only if (w, v) e E. We will occasionally call a loop a 1-edge and an edge that is not a loop a 2-edge. Moreover, given a graph G, we will refer to its vertex set as V (G) and to its edge set as E (G).
Definition 1.1. Let Gi,..., Gk be graphs. The Cartesian product G = Gi □ • • • □ Gk is a graph with vertex set V(G) = V(G1) x • • • x V(Gk), and edge set E(G) defined as follows: two vertices (v1,..., vk) e V(G) and (w1,..., wk) e V(G) are adjacent if there exists an index i such that (v^ wj) e E(Gj), and vj = wj for all j = i.
Note that this definition extends the classical one for simple graphs. The product graph has a loop on a vertex (v1,..., vk) e V(G) if and only if there is a loop on at least one of the constituents vj e V(Gj). Thus, the distribution of loops (or 1-edges) on the product graph is independent from the distribution of the 2-edges.
Definition 1.2. Let G1,..., Gk be graphs, and G = G1 □ • • • □ Gk. The ith projection Pi : V(G) ^ V(Gj) is given by (v1,..., vfc) ^ vj.
Using Definition 1.1, we observe the property that the projections pj : V(G) ^ V(Gj) are weak homomorphisms from G to Gj. Recall that a weak homomorphism between graphs G and H is a map ^ : V(G) ^ V(H) such that, whenever (v, w) e E(G), either (y(v), y(w)) e E(H) or <^(v) = y(w). In particular, the presence of loops in G or H does not impose any restriction on a weak homomorphism from G to H.
Definition 1.3. Let G1,..., Gk be graphs, and G = G1 □ • • • □ Gk. For every vertex a = (a1,..., ak) e V(G), the Gj-layer through a is the induced subgraph
G" = (jx e V (G) | Pj (x) = aj for j = i}> = (j(a1,a2,...,xj,...,ak) | Xj e V(Gj)}>.
Note that G" = Gb if and only if pj (a) = pj (b) for each index j = i. With the usual Cartesian product, the restrictions pj|V(G") : V(G") ^ V(Gj) are isomorphisms between G" and Gj [1, Section 4.3]. Under Definition 1.1, we obtain a dichotomy, as follows.
Lemma 1.4. Let G1,..., Gk be graphs, and G = G1 □ • • • □ Gk. Then, the following two conditions hold for every vertex a = (a1,..., ak) e V (G) and every i e j1,..., k}:
(i)	If aj e V (Gj) is unlooped for every j = i, then pj|V (G") : V (G") ^ V (Gj) is an isomorphism between G" and Gj.
(ii)	Otherwise, G" is isomorphic to Gj with a loop attached to every vertex.
Proof. Easy from the definitions.	□
T. Boiko et al.: The Cartesian product of graphs with loops
3
2 Matrix and semiring properties
From the definition of the Cartesian product we infer that it is commutative and distributive over the disjoint union. Moreover, the trivial graph Ki, that is, a vertex without edges, is a unit. As the Cartesian product is also associative, see below, the set r0 of isomorphism classes of finite undirected graphs with loops is a commutative semiring.
To prove associativity we could adapt the proof of [1, Proposition 4.1] for associativity of the Cartesian product of graphs without loops, or we could modify the multiplication table method of [1, Exercise 4.15], which was introduced for the classification of associative products. However, we follow a different path and use the fact that the adjacency matrix A(G □ H) of the Cartesian product of two simple graphs is the Kronecker sum of the adjacency matrices A(G) and A(H) of the factors, see [1, Section 33.3].
Let us first recall that the Kronecker sum A © B of an n x n matrix A by an m x m matrix B is defined as In < B + A < Im. Here, In and Im denote the identity matrices of size n and m, respectively, and P ( Q denotes the Kronecker product. In our situation, the first factor P = (pj) is always an n x n matrix and the Kronecker product is defined by
P ( Q
PllQ ••• PlnQ
PnlQ • • • PnnQ
Notice that both the Kronecker sum and the Kronecker product are associative but not commutative.
For simple graphs G and H we have A(G □ H) = A(G) © A(H). For graphs with loops we find that the diagonal entries take positive integer values that are not restricted to {0,1}. If we agree on the convention that a positive diagonal entry in the adjacency matrix means a loop, whereas a 0 means no loop, then the product given in Definition 1.1 still corresponds to the Kronecker sum. It follows that, up to isomorphism of graphs, this product is associative.
We note in passing that the fact that the Kronecker sum is not commutative does not contradict the commutativity of the Cartesian product: A(G) © A(H) and A(H) © A(G) represent adjacency matrices of G □ H for different vertex numberings.
Finally, we briefly call a graph entirely looped if every vertex has a loop. For any graph G, we let N(G) be G with its loops removed.
Lemma 2.1. Let G, H, H1, H2 be graphs. Assume that G is entirely looped. Then G □ H is entirely looped as well. Moreover, if N(H1) = N(H2), then G □ H1 = G □ H2.
Proof. The first statement follows directly from Definition 1.1. As remarked earlier, the 2-edges of the products G □ H do not depend on the loops of either factor. Thus
N(G □ Hi) = N(G) □ N(Hi) = N(G) □ N(H2) = N(G □ H2).
Next, we insert the loops on the product; but, as every vertex of G has a loop, it follows that every vertex of either product G □ H has a loop as well, and the two products are obviously isomorphic.	□
4
Ars Math. Contemp. 11 (2016) 35-47
It follows that the subset Too of r0 given by the isomorphism classes of entirely looped graphs constitutes an ideal of the semiring r0. It is obviously closed under the disjoint union and the Cartesian product, and, since the loop K{ is a unit for the Cartesian product inside r00, it is a semiring itself. The loop-removing map N constitutes an isomorphism of semirings between r00 and the set of simple graphs r.
3 Unique factorization
One fundamental property of the Cartesian product, proved independently by Sabidussi [5] and Vizing [6] in the 1960s, is the unique factorization of connected simple graphs into irreducibles with respect to this product. We will extend this result to graphs with loops, where we will have to exclude the set of entirely looped graphs (Lemma 2.1 suggests why). Algebraically speaking, we might want to form the quotient semiring r0/r00, so that also any fully looped components in disconnected graphs are annulled. However, since we will only consider connected graphs in what follows, this is not of great consequence.
Definition 3.1. A nontrivial, connected graph G with at least one unlooped vertex is called irreducible with respect to the Cartesian product if, for every factorization G = H □ L, either H or L is trivial.
Recall that a graph is called trivial if it is a vertex without edges. Consider a nontrivial, connected graph G with at least one unlooped vertex. One can easily check that, if G is not irreducible, it can be expressed as Cartesian product of two factors each of which is, again, a nontrivial, connected graph with at least one unlooped vertex. Iteration of this procedure yields a representation of G as a product of irreducible graphs. It is occasionally called a prime factorization.
Another way to prove the existence of a prime factorization is the following: Any factorization of G with a maximum number of nontrivial factors must be a product of irreducible graphs. If G has n vertices, this maximum number is at most log2(n). Our main results are the following.
Theorem 3.2. Every nontrivial, connected graph with at least one unlooped vertex has a representation as a product of irreducible graphs with respect to the Cartesian product. The representation is unique up to isomorphisms and the order of the factors.
Theorem 3.3. The unique prime factorization with respect to the Cartesian product of a nontrivial, connected graph G with at least one unlooped vertex can be computed in O(m) time, where m is the number of edges of G.
To prove Theorem 3.2, we follow the method of [1, Section 6.1], for Theorem 3.3 we extend the ideas of [4]. First, let us define convex subgraphs and boxes.
Definition 3.4. A subgraph H of a graph G is convex in G if every shortest path in G that connects two vertices of H is completely contained in H. A subgraph H of a Cartesian product G = Gi □ • • • □ Gk is called a box or subproduct if there are subgraphs H C Gj such that
H = Hi □ • • • □ Hk .
In order to determine whether a subgraph is convex or not, only the 2-edges need to be concerned. In particular, a subgraph H is convex in G if and only if the subgraph N(H) is convex in N(G).
T. Boiko et al.: The Cartesian product of graphs with loops
5
Gi
H i
< <6 *> >
H2
Figure 1: An isomorphism between factored graphs with loops.
Lemma 3.5. Let H be a subgraph of a Cartesian product G = G\ □ the following are equivalent:
□ Gk. Then
(i)	H is an induced and convex subgraph of G;
(ii)	There are induced and convex subgraphs Hi C Gi such that H = Hi □ In other words, H is a box whose factors are induced and convex.
□ Hk.
Proof. As far as only the 2-edges are concerned, all convex subgraphs are induced and the assertion is Lemma 6.5 of [1]. This means that p1(V(H)) x • • • x pk(V(H)) = V(H). Now, let Hi be the subgraph of Gi induced by pi(V(H)), where i e {1,..., k}. Then the lemma follows by the definition of the Cartesian product.	□
As remarked after Definition 3.1 every finite graph has a factorization into irreducibles. Thus we only have to show that it is unique in order to prove Theorem 3.2. The next lemma and its corollary makes this precise; the situation is illustrated in Figure 1.
Lemma 3.6. Let < be an isomorphism between nontrivial, connected graphs G and H with at least one unlooped vertex. Assume that G and H are representable as products G = Gi □ • • • □ Gk and H = Hi □ • • • □ H of irreducible graphs. Then k = Í and, for every unlooped vertex a e V (G), there is a permutation n of {1,... ,k} such that
<(G?) = H^ for every i e{1,...,k} .
Formally, < is a bijection between the vertex sets V(G) and V(H). But since < is a homomorphism of graphs, it induces a well-defined mapping between the edge sets E(G) and E(H). In the above theorem, we slightly abuse notation and denote the image of the subgraph Ga, including vertices and edges, by <(Gf).
e V (G), and set (bi, ...,b£) := y>(a). = Hj for every i and j. Every layer G" is
Proof. Fix an unlooped vertex a = (ai,... ,ak) By Lemma 1.4 we infer that G" = Gi and Hj(a) = induced and, as a consequence of Lemma 3.5, convex in G. So, its image y(G") is induced and convex in H. Again, as a consequence of Lemma 3.5, f(G") = U\ □ • • • □ Ug, where every Uj is induced and convex in Hj. But y(G") = G" = Gi is irreducible. Since
6
Ars Math. Contemp. 11 (2016) 35-47
(bi,...,be) = ((a) G f(Ga), we conclude that V(Uj) = {bj} for all indices but one, say
jip{a)
n(i). In other words, f(Ga) C H^if. But then
Ga C	) .
Because the latter graph is induced and convex, it is a box; and because it is irreducible, it must be contained in Ga. Therefore, f(Ga) = H^i)
We claim that the map n : {1,..., k} ^ {1,..., 1} is injective. If n(i) = n(j), then
?(Ga) = = Hj = ^(Ga).
But ( is an isomorphism, and therefore the above equation implies Ga = Ga. Since every layer contains at least two vertices, we obtain i = j. So, n is injective, and k < I.
Repetition of the above argument for yields I < k. So, k = I and n is a permutation.
□
Corollary 3.7. Gi = H^) for every i G {1,..., k}.
Proof. Since a is unlooped, Gj = Ga and Hj = Hj(a) for every i and j. By Lemma 3.6 the corollary follows.	□
Clearly Lemma 3.6 and Corollary 3.7 prove the validity of Theorem 3.2.
A remark about automorphisms
In Lemma 3.6 the permutation n of {1,..., k} is constructed to a fixed unlooped vertex a G V(G). Actually n is independent of the choice of a, and one can extend Lemma 3.6 to the following description of the automorphisms of G.
Theorem 3.8. Suppose ( is an automorphism of a nontrivial, connected graph G with at least one unlooped vertex and prime factorization G = Gi □ • • • □ Gk. Then there are a permutation n of {1,..., k} and isomorphisms (i : Gn(j) ^ Gi for which
C(Xl,...,Xfc) = ((i(xn(1)),...,dfc(xn(fc))) .
The proof of this theorem can be led on the same lines as that of [1, Theorem 6.10]. Among other consequences this implies that the automorphism group of G is isomorphic to the automorphism group of the disjoint union of the prime factors Gi,..., Gk.
4 Algorithms
In this section we present two algorithms for the decomposition of a nontrivial, connected graph G with at least one unlooped vertex into its prime factors. One is straightforward and has complexity O(mn), where m is the number of edges and n the number of vertices of G. The other one is linear in the number of edges of G and depends on the algorithm of Imrich and Peterin [4] for the prime factorization of graphs without loops.
Let G = Gi □ • • • □ Gk be the prime factorization of a nontrivial, connected graph G with at least one unlooped vertex. Then also N(G) = N(Gi) □ • • • □ N(Gk). Clearly
T. Boiko et al.: The Cartesian product of graphs with loops
7
the graphs N(Gj), i G {1,..., k}, need not be irreducible with respect to the Cartesian product. Let N(Gj) = H^ □ • • • □ H^) be their prime factorizations. Thus
k i{i)
n (g)=nn Hj,j
i=! j = !
is a representation of N(G) as a Cartesian product of irreducible graphs. Because the prime factorization is unique, it is the prime factorization of N(G), up to the order and isomorphisms of the factors. In other words, if Jj J Zj is a prime factorization of N (G), then there is a partition J = J! U • • • U Jk such that N(Gi) = J] j e j Zj. Our task is to find this partition. We begin with a straightforward approach and prove the following lemma.
Lemma 4.1. Lei G be a nontrivial, connected graph with at least one unlooped vertex. Then its prime factorization can be found in O(mn) time.
Proof. If G has n vertices, then this is also true for N(G), and so the number of factors of N(G), say r, is at most log2(n). This also bounds the size of J and implies that the number s of subsets of J is at most 2log2(n), i. e. s < n. Notice that the factors of N(G) can be found in O(m) time by [4].
Let J!, J2,..., Js be all subsets of J, ordered in such a way that | Ji | < | Jj | whenever 1 < i < j < s. For every i G {1,..., s} set Yj := njeJi Zj and Yj* := njeJ\Ji Zj. Let (Ya)G denote the subgraph of G induced by the layer Yja of Yj through a, and define ((Yj* )a)G analogously. If the partition Jj U (J \ Jj) of J leads to a factorization of G, then (Yja)G is isomorphic to a factor of G.
We begin the algorithm by scanning the Jj in the given order. For every Jj and every vertex v G V (G) we consider the projections (v) and (v) into (Yja)G and ((Yj*)a)G. If v = (v!,..., vr), then (v) = (w!,..., wr), where Wj = Vj if j G Jj, and Wj = aj otherwise. Notice that (v) is the vertex of shortest distance from v in (Yja) G. The other projection (v) is defined analogously. Again, (v) is the vertex of shortest distance from v in ((Y*)a)G. Clearly G = (Yja)G □ ((Yj*)a)G if and only if for every vertex v g V(G) the following two conditions are satisfied:
1.	If v is unlooped, then both (v) and(v) are unlooped.
2.	If v has a loop then at least one of the vertices (v), (v) has a loop.
The time necessary to compute (v) and (v) for a given v is proportional to r. As one can check in constant time whether (v) or (v) has a loop, one can check in O(nr) time whether G = (Y/)G □ ((Yj*)a)G'.	*
Notice that r is the number of factors of N(G), which is also bounded by the minimum degree S of N(G). This is easily seen, since every vertex meets every layer and, in a connected graph, is incident with at least one edge of that layer. Hence the number of factors cannot exceed the degree of any vertex, and nr < nS < m.
For a given Jj one can thus check in O(m) time whether (Yja) G is a factor of G. If it is, and if Jj is minimal with respect to inclusion, then it clearly is an irreducible factor. Hence, this is true for the first factor that we encounter, because of having ordered the Jj by size. We now continue the scan, omitting the Jj that are not disjoint from Jj, to find the next factor. Clearly it will also be irreducible. We continue until we have found all irreducible factors. Since there are no more than n subsets of J, we can find them in O(nm) time. □
8
Ars Math. Contemp. 11 (2016) 35-47
In order to reduce the complexity to O(m), we need some more preparation. So let a be an unlooped vertex of G and L be the levels of a BFS-ordering of the vertices of G with respect to the root a. That is, L consists of all vertices of distance i from a. Furthermore, we enumerate the vertices of G by giving them so-called BFS-numbers that satisfy BFS(v) > BFS(u) if the distance from a to v is larger than the one from a to u.
It is important to observe that the projection pYi (v) is a vertex of {Yia)G and always closer to a than v, unless v already is a vertex of {Yia)G, because then pYi (v) = v.
Proof of Theorem 3.3. Let f]jeJ Zj be a prime factorization of N(G). We begin with the trivial partition of J and wish to check, whether it already leads to a factorization of G. We scan the vertices v of G in BFS-order and, given v, check the validity of Conditions
(i)	If v is unlooped, then all pYi (v) are unlooped.
(ii)	If v has a loop, then at least one of the projections pYi (v) has a loop.
If one of these conditions is not satisfied, then the partition of J is obviously inconsistent with the loop structure. In either case we have too many factors and have to make the partition of J coarser. Before we go on, notice that in Li these conditions are trivially satisfied for any partition of J, because all projections pYi (v) are a, except one, which is v.
Suppose we arrive at a vertex v where one of the conditions (i) or (ii) is violated for the first time. Assume first that Condition (i) is violated, that is, v is unlooped, but pYi (v) has a loop for an index i. In the end, all projections have to be unlooped. We must combine the set Jj with one or more other sets of the partition. Using the fact that we proceed in BFS-order, it is easy to see that we have to make v a unit layer vertex, that is, we combine all those sets Jj for which pYj (v) = a. Assume now that Condition (ii) is violated, that is, v has a loop, but no pYi (v) does. In the end, at least one of the projections has to have a loop. As above, the only way to achieve this is to make v a unit layer vertex, that is, we combine all factors Jj for which pYj (v) = a.
In both cases we arrive at a coarser partition of J than the one we started out with. By associativity of the Cartesian product with loops, we need not recheck the vertices we have already considered and continue in BFS-order.
Notice that this process yields a factorization, because both (i) and (ii) are satisfied. For every finer partition of J one of these conditions is violated, hence the factorization is the unique prime factorization we are looking for.
Considering the computational cost of these operations, we observe that all projections that we need for the n vertices can be computed, in O(n| J|) time. Since we can check in constant time whether a vertex has a loop or not, the checks for conditions (i) and (ii) can also be done in O(n|J|) time. As |J| < J, we have O(n|J|) = O(nJ) = O(m).
Finally, recomputing the partition needs at most O( | J|) time, and this has to be done at most | J| times, so the cost is O(J2).	□
5 Remarks
In [2] it was shown that connected set systems, or hypergraphs, as they are called now, also have unique prime factorizations with respect to the Cartesian product if one-element sets, or loops in our terminology, are excluded. Our result also extends to hypergraphs with loops: Connected hypergraphs have unique prime factorization with respect to the Cartesian product, if there is a least one vertex without a loop. Furthermore, the same
T. Boiko et al.: The Cartesian product of graphs with loops
9
arguments yield unique prime factorization for connected infinite graphs or hypergraphs with respect to the weak Cartesian product; compare [3].
References
[1]	R. Hammack, W. Imrich, and S. Klavzar, Handbook of product graphs, Second Edition, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2011.
[2]	W. Imrich, Kartesisches Produkt von Mengensystemen und Graphen, Studia Sci. Math. Hungar. 81 (1967), 285-290.
[3]	W. Imrich, Über das schwache Kartesische Produkt von Graphen, J. Combinatorial Theory Ser. B 11 (1971), 1-16.
[4]	W. Imrich and I. Peterin, Recognizing Cartesian products in linear time, Discrete Math. 307 (2007), 472-483.
[5]	G. Sabidussi, Graph multiplication, Math. Z. 72 (1960), 446-457.
[6]	V. Vizing, The Cartesian product of graphs (Russian), Vycisl. Sistemy 9 (1963), 30-43. English translation in Comp. El. Syst. 2 (1966), 352-365.