ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 7 (2014) 487-497
Fast recognition of direct and strong products*
Richard H. Hammack
Department of Mathematics and Applied Mathematics, Virginia Commonwealth University, Richmond, Virginia, USA
Wilfried Imrich
Department Mathematics and Information Technology, Montanuniversität Leoben, A-8700 Leoben, Austria
Received 9 April 2012, accepted 17 May 2014, published online 24 September 2014
This note describes fast algorithms for computing the prime factors of connected, non-bipartite graphs with respect to the direct product, and of connected graphs with respect to the strong product. The complexities are O(mmin(n2, A3)) for the direct product, and O(m a(G)A) for the strong, where n is the order of the graph G to be factored, m its size, a(G) its arboricity, and A its maximum degree. That is, the complexities are linear in m for fixed A.
Keywords: Graph products, algorithms. Math. Subj. Class.: 05C85, 05C75, 05C12
1 Introduction
The Cartesian, direct, and strong products of graphs are the only nontrivial, associative products defined on the Cartesian products of the vertex sets having the property that the projections onto the factors are weak homomorphisms [4]. These products enjoy many interesting algebraic properties, such as unique prime factorization. Connected graphs have unique prime factor decompositions with respect to the Cartesian and the strong product in the class r of simple graphs [9, 10, 1, 7], and connected nonbipartite graphs have unique prime factor decompositions with respect to the direct product in the class r0 of graphs where loops but not multiple edges are allowed [7].
* This paper is a part of Bled'11 Special Issue.
E-mail addresses: rhammack@vcu.edu (Richard H. Hammack), imrich@unileoben.ac.at (Wilfried Imrich)
Abstract
©® This work is licensed under http://creativecommons.Org/licenses/by/3.0/
488
ArsMath. Contemp. 7(2014)487-497
In the case of the Cartesian product the prime factors can be computed in linear time, that is, in O(m) time, where m is the size of the graph; see [6].
For the other two products the situation is different. For the strong product the paper [2] by Feigenbaum and Schaffer was the first that presented a polynomial algorithm for the unique factorization of connected graphs. This was then extended to the factorization of nonbipartite connected graphs with respect to the direct product by Imrich [5]. In both papers the main aim was to show that the factorization was possible in polynomial time, hence neither of [2, 5] contains an estimate of the complexity of the algorithm presented there. A rough estimate shows that it is O(n4 5) in [2] and O(n5) in [5], where n is the order of the graph.
Both algorithms depend on the factorization of auxiliary graphs with respect to the Cartesian product. The auxiliary graphs are called Cartesian skeletons and are defined algorithmically in [2, 5]. The algorithmic definition makes it difficult to work with them.
Later, non-algorithmic definitions were given [3], along with efficient algorithms that compute them. However, it was not known whether it was possible to find the prime factors with respect to the direct and the strong products within the same time complexities needed for computing the skeletons.
The present paper shows that this is indeed the case. We prove that connected, nonbipartite graphs can be factored over the direct product in O(m min(n2, A3)) time, and that the prime factors of connected graphs with respect to the strong product can be found in O(ma(G)A) time, where n is the order, m the size, A the maximum degree, and a(G) the arboricity of the graph G that is to be factored. (The arboricity a(G) of a graph G is the minimum number of forests into which E(G) can be partitioned. It is easily seen that a(G) < A.)
Although both algorithms that are presented here have complexities close to O(n4) in the worst case, which just slightly better than that of the algorithms of Feigenbaum and Schaffer [2] (for the strong product) and of Imrich [5] (for the direct product), their main advantage is that their complexities for graphs with known bounds on the maximum degree or the arboricity (in the case of the strong product) and can be explicitly stated.
In particular, we wish to point out that, for fixed A and growing m, we have m < nA, hence n also grows, and A3 must eventually become smaller than n2. Also note that a(G)A < A2. Hence the complexities grow linearly in m for fixed A. Algorithms with such complexities are called quasilinear.
On the way, in Section 2.1, we also prove new bounds on the number of prime factors of a graph with respect to the strong and the direct product.
2 Definitions
We consider finite graphs G which may have loops but not multiple edges, and denote the class of these graphs by r0, while r c r0 is the class of graphs without loops. An edge joining g to g' is denoted gg'. The open neighborhood of a vertex g is denoted N(g), or NG(g) when it is necessary to indicate the graph under discussion. The closed neighborhood of g is N[g] = N(g) U {g}. Again, we often write this as NG[g].
Given graphs H and K, the Cartesian product H □ K, the direct product H x K and the strong product H K K, are defined on the Cartesian product V (H) x V (K) of the
Richard H. Hammack and Wilfried Imrich: Fast recognition of direct and strong products 489
vertex sets of the factors and have the following edge sets:
E(H □ K) = {(h,k)(h',k') | hh' G E(H),k = k', or h = h',kk' G E(K)}, E(H x K) = {(h,k)(h',k') | hh' G E(H) and kk' G E(K)}, E(H m K) = E(H □ K) U E(H x K).
(Examples are shown in Figure 1.) All three products are commutative and associative. Also, the complete graph Ki on one vertex is a unit for □ and m, as Ki □ H = H and Ki m H = H for all graphs H. The graph K'{ consisting of a single vertex with a loop satisfies KI x H = H, and is the unit for x.
K
H DK
K
H
HK
H
K
H H K
H
Figure 1: The three standard graph products
y
u
v
x
Let a = (a1, a2,..., ak) be a vertex of a product G = G1 * G2 * ■ ■ ■ * Gk, where * designates any of the symbols □ , x, or m. Then the Gj-layer G" of Gj through a is defined as the subgraph of G induced by the set of vertices
{(ai, a2,. .., aj-i, Xj, ai+i .. ., ak) | Xj G V(Gj)} .
For the Cartesian and the strong product, the Gj-layers are isomorphic to Gj. For the direct product, G" = Gj if all aj have a loop in Gj for j = i. Otherwise G" has no edges.
We call the mapping a ^ aj a projection. For a subgraph H of G, it restricts to a mapping pj : H ^ Gj. For the direct product this is a homomorphism; for the other two products it is a weak homomorphism1.
If X C V(G), the subgraph of G induced on X is denoted (X}, or (X}G if there is a risk of ambiguity. As a consequence of the definitions, if Xj C V(Gj) for 1 < i < k, then
(Xi x X2 x ■ ■ ■ x Xk}Gl □ g2 □ ... □ Gk = (Xi}Gl □ (X2}g2 □ ■ ■ ■ □ (Xk}Gfc, (2.1)
where the x indicates the Cartesian product of sets.
A nontrivial graph is called prime with respect to a particular product if whenever it is represented as a product of two factors, one of the factors is the unit for the product. As already mentioned, connected graphs have unique prime factor decompositions with respect to the Cartesian and the strong product in r, and connected nonbipartite graphs have unique prime factor decompositions with respect to the direct product in r0.
There are two significant equivalence relations R and S on the vertex set of a graph. To motivate this, note that Cartesian products possess a certain degree of rigidity; any automorphism of H □ K is induced by automorphisms of H and K (or their transposition
1 Recall that a homomorphims is an edge-preserving map, whereas a weak homomorphims either preserve edges or maps them into single vertices.
402	Ars Math. Contemp. 7 (2014) 379-187
Figure 2: Left: Graphs H,K,H x K (solid) and Hs,Ks, (H x K)s (dotted). Right: Graphs H, K, H x K (solid) and Cartesian skeletons S(H), S(K), S(H x K) (dotted).
if they are isomorphic). This is not so with the direct and strong products. For example, in Figure 1 the vertices u and v of H x K can be transposed. The same is true for x and y in H K K. It is easy to see the reason for this. In the case of the direct product, the interchange is possible because N(u) = N(v); it is possible for the strong product because N[x] = N[y]. We declare that two vertices x, y are in relation R if N(x) = N(y), and they are in relation S if N[x] = N[y]. Notice that both R and S are equivalence relations.
We say a graph is R-thin if every R-equivalence class consists of a single vertex; it is S-thin if every S-equivalence class has a single vertex. In discussions of prime factoring over the direct product, it is helpful (at least initially) to assume that all graphs are R-thin. For the strong product, we assume S-thinness.
Another important concept is the Boolean square. The Boolean square Gs of a graph G has vertex set V(Gs) = V(G) and edges E(Gs) = {xy | NG(x) n NG(y) = 0}. The left side of Figure 2 shows graphs H, K and H x K (bold) and their Boolean squares (dotted). It is easy to confirm that
(Gi x G2)s = G1 x G2, and this is indeed reflected in the figure. Furthermore, letting NG denote the graph G after removal of all loops, we have
N((Gi x G2)s) = NGi KNG2.	(2.2)
The most important concept in this paper is a certain subgraph of Gs called the Cartesian skeleton. It is obtained from Gs by removal of the so-called dispensable edges.
We call an edge xy of Gs dispensable if x = y or if there exists some z G V(G) for which both of the following statements hold.
1.	Ng(x) n NG(y) C Ng(x) n Ng(z) or NG(x) C NG(z) C NG(y),
2.	NG(y) n Ng (x) C NG(y) n Ng(z) or NG(y) C Ng(z) C Ng(x).
In Figure 2 (left) the edge xy is dispensable because NG (x) nNG (y) C NG (x)nNG (z) and NG(y) nNg(x) C NG(y) nNg(z). Also, x'y' is dispensable, as Ng(x') C Ng(z') c NG(y') and NG(y') n Ng(x') C NG(y') n NG(z').
Richard H. Hammack and Wilfried Imrich: Fast recognition of direct and strong products 489
K
H IE K
S[K] S[H I K] = S[H]aS[K]
	c\	/y \
		
H
'S[H ]
Figure 3: Left: Graphs H, K, H
S [H M K].
K; Right: Closed Cartesian skeletons S[H],S[K],
The Cartesian skeleton of a graph G is the graph S(G) obtained from Gs by removing all dispensable edges. For example, the dotted lines in Figure 2 (right) are the Cartesian skeletons of H, K and H x K. This figure illuminates a general principle that was proved in [3]: If the product H x K is R-thin and has no isolated vertices, then
S(H x K) = S(H) □ S(K).
(2.3)
For the strong product a similar construction, the closed Cartesian skeleton S[G], is useful. It is a subgraph of G obtained by removing all dispensable edges of G, where an edge xy of G is dispensable if for some z G V (G) both of the following conditions hold:
1	(strong).
2	(strong).
NG[x] n NG[y] NG[y] n NG[x]
Ng [x] n Ng[z] Ng [y] n Ng[z]
or Ng[x] C Ng[z] C NG[y], or NG[y] C Ng[z] c Ng[x].
Figure 3 shows graphs H, K and H M K on the left and their closed Cartesian skeletons S[H], S[K] and S[H M K] on the right. Notice the edge xy (for example) is dispensable, because Ng [x] n Ng [y] C Ng [x] n Ng [z] and Ng [y] n Ng [x] C Ng [y] n Ng [z] . Also, x'y' is dispensable, as Ng [x'] C Ng[z'] c NG[y'] and NG[y'] n Ng [x'] C Ng^'] n Ng [z']. If H M K is S-thin, then, similarly to Equation (2.3), we have
S[H M K] = S[H] □ S [K],
(2.4)
as noted in reference [3], in which it is also shown that the Cartesian skeletons of connected nonbipartite graphs are connected. Moreover, the condition of nonbipartiteness can be dropped in the case of the closed Cartesian skeleton: S[G] is connected if G is.
Note that Equations (2.3) and (2.4) express equality of graphs, not just isomorphism. That is, e.g., graphs S(H x K) and S(H) □ S(K) have identical vertex sets and edge sets.
The article [3] also presents algorithms and complexity analysis for computing S(G) and S[G]. The skeleton S(G) can be computed in min{O(mn2), O(mA3)} time. Its space complexity is determined by the size of the output and is thus between O(n) and O(n2).
On the other hand, the closed Cartesian skeleton S[G] can be computed in O(m a(G)A) time, where a(G) is the arboricity of G, that is, the minimum number of forests into which
z
x
488
ArsMath. Contemp. 7(2014)487-497
the E(G) can be partitioned. One can show that 5/2 < a(G) < A, where 5 is the minimum degree of G.2
2.1 Bounds on the number of factors
We will need bounds on the number of prime factors of graphs relative to different products.
A simple computation shows that a product of k nontrivial graphs has at least 2k vertices. In other words, a graph on n vertices can have at most log2 n factors with respect to any product. However, note that the strong product of k copies of K2 is K2k, and that every vertex has degree 2k - 1. Thus any vertex of a strong product of k nontrivial connected factors has degree at least 2k - 1.
For the Cartesian product it is well known that a connected graph has at most 5 factors.
Lemma 2.1. Suppose a graph G has n vertices and minimum degree 5. Then:
1.	G has at most log2 n factors with respect to the Cartesian, direct, or strong product.
2.	If G is connected, it has at most 5 factors with respect to the Cartesian product.
3.	If G is connected, it has at most log2 (5 +1) factors with respect to the strong product.
Proof. We have already addressed the first two statements. If G is connected, then so are all of its strong product factors. If G has k factors, then 5 > 2k -1, so log2 (5 +1) > k. □
For the direct product we have the following corollary.
Corollary 2.2. A connected, nonbipartite graph has at most log2(5A + 1) factors with respect to the direct product.
Proof. Let G = Gi x G2 x • • • x Gk. Then Gf = Gf x G2 x • • • x G|, so any bound on the number of factors of Gf also bounds the number of factors of G. Equation (2.2) implies
Hence k is also bounded by the number of factors of NGf over the strong product. As log2(5_N+ 1) > k, the assertion will follow as soon as we establish 5GAG > 5ng= .
Indeed, for any vertex x of NGf the definition of Gf yields degG (x)AG > degnGs (x). If x has minimum degree in G, this is 5G AG > degnGs (x); thus 5G AG > 5nG=. □
ATGs = TV Gf
TVGf
A/Gf
i
2
k
3 Thin graphs and the direct product
Suppose we want to compute the prime factorization G = Gf x G2 x • • • x Gk of an R-thin, connected, nonbipartite graph G. The compatibility of the Cartesian skeleton with the direct product as expressed in Equation (2.3) implies
S(G) = S(Gi) □ S(G2) □ • • • □ S(Gk).	(3.1)
Because S(G) is connected, there is a Cartesian prime factorization
S (G) = □ Hi	(3.2)
iei
2 These relations are not hard to show. The right side is routine.	For the left side one invokes a theorem of Nash-Williams [8], see [4, Exercise 20.2] and the hint thereto.
Richard H. Hammack and Wilfried Imrich: Fast recognition of direct and strong products 489
that is unique up to the order and isomorphisms of the factors. By [4, p. 296], this equals the presentation in (3.1) or a refinement of it. Thus the number of Cartesian factors of S(G) can be larger than the number of direct factors of G. Since we can compute S(G) and its prime factorization over □ , our task is to find a partition J1, J2,..., Jk of I such that
S (Gi) = □ Hj
jeJi
for all i, 1 < i < k.
Section 24.3 of [4] shows that each J is a minimal subset of I for which the HJi -layers
of HJi □ Hi\Ji (where HJi = □ jeJi Hj and Hi\Ji = □ jei\Ji Hj) correspond to the layers of a factor of G with respect to the direct product. In other words, each J is a minimal subset of I for which G = pJi(G) x pI\Ji (G), where pJi is the projection of V(G) = V(S(G)) onto V(HJi ),andpJi (G) is the smallest graph for which this projection is a homomorphism. (The graph pI\ Ji (G) is defined similarly.)
It is also shown there that the complexity of checking whether a subset J C I induces a factoring G = pJ(G) x pI\J(G) is O(m |11). As I has 2111 subsets, the complexity of checking them all is O (m 2|I||1 |).
Now, the Cartesian skeleton S(G) has the same number of vertices as G. By Lemma 2.1, we infer that |11 < log2 n. Hence the prime factors of G with respect to the direct product can be computed from the Cartesian skeleton in O(m2log2 n log2 n) = O(mn log n) time.
Recall that the Cartesian skeleton can be computed in min{O(mn2), O(mA3)} time. Clearly O(mnlog n) < O(mn2), so if nlog2 n < A3, then the prime factorization of G over the direct product (from S(G)) does not cost more than the computation of S(G). But, if A3 < n log2 n, then the computation of the Cartesian skeleton is cheaper than the computation of the prime factorization as presented above.
If we could somehow reduce the number of subsets of I that must be investigated, then we might be able to retain the time complexity O(mA3) for the prime factorization of G even when A3 < n log2 n. This is indeed possible.
But before stating it in the next proposition, we first recall an elemental fact about vertex neighborhoods in direct products, namely if G = Gi x G2 x • • • x Gk, then
NG((ai,a2,... ,afc)) = NGl (ai) x Nq2 («2) x • • • x NGk (afc),	(3.3)
where x is the Cartesian product of sets. Taking induced subgraphs, this becomes
(Ng(K,«2,...,afc)))g = (Ng!(ai)>G! x (Ng2M)g2 x ••• x (Ng&(afc)>Gfc, (3.4)
where x is the direct product of graphs. A subgraph of a product that is a product of subgraphs of the factors is called a box relative to the product. The above equation implies that the subgraph induced on any open neighborhood of a graph is a box relative to any direct product factorization of the graph.
Proposition 3.1. If G is a connected, nonbipartite R-thin graph of order n and size m, then its direct product prime factorization can be found in min{O(mn2), O(mA3)} time.
Proof. By the above arguments it suffices to treat the case A3 < n2; see also [4, p. 296].
488
ArsMath. Contemp. 7(2014)487-497
Let us have a closer look at the Cartesian skeleton of a graph G with prime factorization Gi x G2 x • • • x Gk .By our previous discussion we have:
G = G1 x G2 x • • • x Gk,	(3.5)
S(G) = S(Gi) □ S(G2) □ ••• □ S(Gfc),	(3.6)
Gf = Gi x G2 x • • • x Gk.	(3.7)
Furthermore, given a G V(G), the layers Ga, S(Gj)° and (Gf )a have the same vertex sets. Moreover, the layers (Gf)a are all isomorphic to Gf. Given v G V (Gs), Equation (3.4) applied to (3.7) gives
k
(Ngs (v))G. = X (Ngs (vj))gj.	(3.8)
i=i
Notice that all (NG= (vj))gj are connected, but that they need not be prime (with respect to the direct product), and that the Gf may not be R-thin.
Equation (3.3) applied to (3.7) gives NGs (v) = NG^ (v1) x NG^ (v2) x • • • x NG£ (vk). Consider the subgraph of S(G) = S(Gi) □ S(G2) □ • • • □ S(Gk) induced on this vertex set. Using Equation (2.1), we get
k
(Ngs (v))s(G) = □ (NgS (vi))s(Gi).	(3.9)
i=1
Call this box S(G)(v).
Comparing Equations (3.9) and (3.6), we see that S(G)(v) contains all edges of S(Gj)v that are incident with v for any i. Thus, the connected component of S(G)(v) through v contains edges from all S(Gj). Clearly it is a box, and we denote it by B. By Equation (3.9) we have
S(G) = S(Gi) □ S (G2) □ ••• □ S(Gk) Ul	Ul	Ul	Ul	(3.10)
B = Bi □ B2 □ • • • □ Bk.
Observe that the number of vertices of S(G)( v) is the same as the number of vertices of NGs (v), which is at most A2, a bound for the maximum degree of Gs. But then the number of Cartesian factors of S(G)(v) is at most 2log2 A, and this also bounds the number of Cartesian factors of B. Thus the factoring of B in Equation (3.10) has a refinement B = Bi □ B2 □ • • • □ B', where I < 2log2 A, and each Bf is a prime factor of some Bj. (Recall that - as mentioned in the introduction - computing the prime factorization of S(G) is linear in m, and hence this is also the case for B.)
From (3.10), we see that each Cartesian prime factor Bf of B is a prime factor of some Bj, and hence i is the only index 1 < i < k for which S(Gj) has prime factors Hj with E(Bfv) n E(Hv) = 0. Form a new partition J', J2,..., J' of I, where Jf consists of indices j G I for which E(B'v) n E(Hv) = 0. This new partition need not be unique, for an E(Hj) may meet layers of several prime factors of B. To be definite, we define the J' inductively by first declaring J' = {j G I | E(Biv) n E(Hv) = 0} and thereafter J' = {j G I - Ua=1 J 'a | E (B'v) n E(HV ) = 0}.
/A=i a 1 ^v-^ f ! 1 1 ^v-1 -'j . Letting the ^ graphs
H' = □ Hj
jeJs
Richard H. Hammack and Wilfried Imrich: Fast recognition of direct and strong products 489
play the role of the H we thus see that we can find the prime factors of G from S(G) in
O(m22 log a2 log A) = O(mA2 log A) = O(mA3) time, which is the same time complexity as that for computing S(G) if A3 < n2. □
4 Thin graphs and the strong product
Let G be a connected S-thin graph. It is uniquely factorable into prime graphs with respect to the strong product, say as
g = Gi mg2 m ■ ■ ■ eGk.
By [3], the strong Cartesian skeleton of G is the Cartesian product of the strong Cartesian skeletons of the Gi, in symbols,
S[G] = S[Gi] □ S[G2] □ ■ ■ ■ □ S[Gk].	(4.1)
Similarly to the case of the direct product, there is a unique prime factorization
S[G] = □ Hi.
iei
It is equal to the the presentation in Equation (4.1) or to a refinement of it. Again our task is to find a partition J1, J2,..., Jk of I such that
S[Gi] = □ Hj jeJi
for all i, 1 < i < k. As before we have to check all minimal subsets Ji of I. We have to ensure that the HJ -layers of HJ □ HI\J (where HJ = □ jeJ Hj and HI\J =
□ jei\Ji Hj) correspond to the layers of a factor of G with respect to the strong product. (Again, see Section 24.3 of [4].)
Here too the complexity of doing this is O(m2log2111 log2 |11). Since the bound log2 n for |11 yields the bound O(mn log n), which will usually be larger than O(m a(G)A), we follow a similar approach as before.
Before beginning, we note that in the case of the strong product, Formulas (3.3) and (3.4) play out as follows. If G = Gi m G2 m ■ ■ ■ m Gk, then
NG[(ai, a2,..., ak)] = NGl [ai] x Nq2 [a2] x ■ ■ ■ x NGk [ak],	(4.2)
where x is the Cartesian product of sets.
Proposition 4.1. Let G be a connected S-thin graph of order n and size m. Then its prime factors with respect to the strong product can be computed in O(m a(G)A) time.
Proof. The proof parallels that of Proposition 3.1. Choose a vertex v of minimal degree in G and consider its closed neighborhood
Ng[v] = Ngi [vi] x NG2 [V2] x ■ ■ ■ x NGfc [vk].
By Equation (2.1), the subgraph of S[G] = S[Gi] □ S[G2] □ ■ ■ ■ □ S[Gk] induced on this vertex set is the box
(NG[v])s[Gj = (NGi [v1])s[Gi] □ (NG2 [v2])s[G2 ] □ ■■ ■ □ (NGfc [vk ])s[Gfc ].
402
Ars Math. Contemp. 7 (2014) 379-187
As before, let B be the component of this box containing v. Then B is a box with no more than S +1 vertices, and it factors as
S [G] = S [Gi] □ S [G2] □ ••• □ S[Gk ] Ul	Ul	Ul	Ul	(4.3)
B = B1 □ B2 □ • • • □ Bk .
This factoring of B has a refinement B = B[ □ B2 □ • • • □ B'£, where i < log2(S + 1), and each B's is a prime factor of some Bj. As in the proof of Proposition 3.1, we can form a new partition J' , J2,..., J' of I, where J's consists of indices j e I for which E(B'Sv) n E(Hj) = 0. Arguing as before, we see that we can find the prime factors of G from S [G] in
O(m2log5 log(S + 1)) = O(mSlogS)
time. From S < 2a(G) we infer that O(mS log S) = O(ma(G)A). The observation that the prime factors of B can be computed in O(SA) time completes the proof.	□
We wish to point out that we have no guarantee that NG [v] is thin, which excludes it from our present factorization methods.
5 Factoring graphs that are not thin
Up to here we have factored only thin graphs. The reason is that we made strong use of properties of the Cartesian skeleton that do not hold if the graphs are not thin. In order to factor a graph G that is not thin we first compute the quotient graphs G/R or G/S. These are formed from G by contracting all R-classes (respectively all S-classes) of G to single vertices. The resulting graphs are thin, and factored by the methods just described. (See Section 8.2 of [4, 24.4].) Notice that one can compute G/R, respectively G/S, in O(m) time.
Once G/R, respectively G/S, has been factored, the question is whether this leads to factorization of G. While every factorization of G induces a factorization of G/R, respectively G/S, this is not true in the other direction. For example, consider the graph G consisting of a triangle C3 on the vertices v0v1v2 and two pendant edges v0a and v0b. It is not R-thin, because the vertices a and b have the same neighborhoods. As G has 5 vertices, it is prime. Contracting the R-class {a, b} to a single vertex, we obtain the thin graph G/R, which is a triangle with one pendant edge. It is easily seen that this graph is the direct product of two copies of an edge with a loop. Similar examples are possible for the strong product.
Hence, we observe that G may have fewer prime factors than G/R, respectively G/S. We now use [4, 24.4] to compute them. First the direct product.
By [4, 24.4], connected, nonbipartite graphs G of size m and order n can be factored with respect to the direct product in O(m2kk) time, where k is a bound on the number of direct factors of G. With the general bound k < log2 n this yields the bound O(mn2) for the factorization of G.
If A3 < n2 we use the bound k < log2 (SA) from Corollary 2.2. It yields the estimate
m2kk < m2log2(5A) log2(SA) < mSA(log2 S + log2 A) < 2mA3 .
Theorem 5.1. The prime factors (over the direct product) of a connected, nonbipartite graph of size m, order n, and maximum degree A can be found in O(m min(n2, A3)) time.
Richard H. Hammack and Wilfried Imrich: Fast recognition of direct and strong products 489
For the strong product we have the same complexity O(m2k k), but here k is the number of strong factors of G. Using the bound log2 (S +1) for k we thus obtain the following.
O(m2kk) = O(m2log2(Ä+1) log2(S + 1)) = O(m(S + 1)S) = O(ma(G)A).
Theorem 5.2. The prime factors (over the strong product) of a connected graph of size m, arboricity a(G), and maximum degree A can be computed in O(m a(G)A) time.
Acknowledgement We thank the two reviewers for thorough and thoughtful reports. References
[1]	W. Dörfler and W. Imrich, Über das starke Produkt von endlichen Graphen, Österreich. Akad. Wiss. Math.-Natur. Kl. S.-B. II, 178 (1970), 247-262.
[2]	J. Feigenbaum and A. A. Schaffer, Finding prime factors of strong direct product graphs in polynomial time, Discrete Math., 109 (1992), 77-102.
[3]	R. Hammack and W. Imrich, On Cartesian skeletons of graphs, Ars Math. Contemp., 2 (2009), 191-205.
[4]	R. Hammack, W. Imrich, and S. Klavzar, Handbook of Product Graphs, Second Edition, Series: Discrete Mathematis and its Applications, CRC Press, 2011.
[5]	W. Imrich, Factoring cardinal product graphs in polynomial time, Discrete Math., 192 (1998), 119-144.
[6]	W. Imrich and I. Peterin, Recognizing Cartesian products in linear time. Discrete Math., 307 (3-5) (2007), 472-483.
[7]	R. McKenzie, Cardinal multiplication of structures with a reflexive relation, Fund. Math., 70 (1971), 59-101.
[8]	C. St. J. A. Nash-Williams, Decomposition of finite graphs into forests, Journal of the London Mathematical Society 39 (1964), 12.
[9]	G. Sabidussi, Graph multiplication, Math Z.., 72 (1960), 446-457.
[10] V. G. Vizing, The Cartesian product of graphs (Russian), Vycisl. Sistemy, 9 (1963), 30-43.