Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 2 (2009) 191–205
On Cartesian skeletons of graphs
Richard H. Hammack
Department of Mathematics and Applied Mathematics
Virginia Commonwealth University, Richmond, VA, USA
Wilfried Imrich
Chair of Applied Mathematics, Montanuniversität Leoben
A-8700 Leoben, Austria
Received 27 July 2009, accepted 9 September 2009, published online 30 September 2009
Abstract
Under suitable conditions of connectivity or non-bipartiteness, each of the three stan-
dard graph products (the Cartesian product, the direct product and the strong product)
satisfies the unique prime factorization property, and there are polynomial algorithms to
determine the prime factors. This is most easily proved for the Cartesian product. For the
other products, current proofs involve a notion of a Cartesian skeleton which transfers their
multiplication properties to the Cartesian product.
The present article introduces simplified definitions of Cartesian skeletons for the direct
and strong products, and provides new, fast and transparent algorithms for their construc-
tion. Since the complexity of the prime factorization of the direct and the strong product
is determined by the complexity of the construction of the Cartesian skeleton, the new al-
gorithms also improve the complexity of the prime factorizations of graphs with respect to
the direct and the strong product.
We indicate how these simplifications fit into the existing literature.
Keywords: Graph product, Cartesian skeleton, prime factorization of graphs, graph algorithms.
Math. Subj. Class.: 05C85, 05C99
1 Introduction
We consider finite graphs G = (V (G), E(G)) which may have loops but not multiple
edges. We let Γ0 denote the class of all such graphs, while Γ ⊂ Γ0 is the class of graphs
without loops. An edge joining g to g′ is denoted gg′.
E-mail addresses: rhammack@vcu.edu (Richard H. Hammack), imrich@unileoben.ac.at (Wilfried Imrich)
Copyright c© 2009 DMFA Slovenije
192 Ars Math. Contemp. 2 (2009) 191–205
We assume our reader is quite familiar with the three standard graph products. Nonethe-
less, as the notation and lexicon are not universal, we collect the definitions and some main
ideas in this introduction. Given graphs H and K, one can form the Cartesian product
H2K, the direct product H ×K and the strong product H K. Each has as a vertex set
the Cartesian product V (H)× V (K) of sets. The edge sets are as follows.
E(H2K) = {(h, k)(h′, k′) : hh′ ∈ E(H), k = k′, or h = h′, kk′ ∈ E(K)}
E(H ×K) = {(h, k)(h′, k′) : hh′ ∈ E(H) and kk′ ∈ E(K)}
E(H K) = E(H2K) ∪ E(H ×K)
These products are significant in that they are the only nontrivial associative and commuta-
tive products whose projections onto the factors are weak homomorphisims. (See Appendix
C of [7].) Figure 1 shows specific examples.
H H H
H2K H ×K H KK K K
x x x
y y
y
Figure 1: The three standard graph products
The one-vertex complete graph K1 serves as a unit for 2 and , as K12H ∼= H and
K1 H ∼= H for all graphs H . The graph Ks1 consisting of a single vertex on which there
is a loop satisfies Ks1 ×H ∼= H , so it is the unit for×. A graph is called prime with respect
to a particular product if whenever it is expressed as a product of two factors, one of the
factors is the unit for the product.
Sabidussi [12] and Vizing [13] first proved that every connected graph in Γ has a unique
factorization over the Cartesian product into prime factors in Γ. (See [8] for a more recent
approach.) Moreover, efficient algorithms exist [4, 9] for determining the prime factors.
Any connected graph in Γ also has a unique prime factorization over the strong product,
a result that was first proved in [3]. Subsequently, this same result was implied by McKen-
zie’s general work [10] on products of relational structures. McKenzie’s results also imply
that the class of connected non-bipartite graphs in Γ0 obey unique prime factorization over
the direct product.
Articles [6, 5] present polynomial algorithms that determine the prime factorizations
of graphs over the direct and strong products, and both approaches are adapted in [7].
These approaches involve construction of a so-called “Cartesian Skeleton,” a graph that
envelops a given graph G in such a way that factorizations of G over × (or ) induce
factorizations of the Cartesian skeleton over 2. This links prime factorizations over × (or
) to factorizations over 2, and algorithms for prime factorization over 2 are then applied
to the Cartesian skeleton and transferred back to factorizations of G over × (or ).
Cartesian skeletons are defined algorithmically in [6] and [5]. Unfortunately, the al-
gorithmic approach makes it difficult to deduce even simple properties of skeletons and
does not even ensure uniqueness. The purpose of the current paper is to provide simple
R. H. Hammack and W. Imrich: On Cartesian skeletons of graphs 193
non-algorithmic definitions of skeletons, and to describe separate algorithms for their con-
struction. Our definitions clarify the structure of skeletons and consequently serve the dual
purpose of simplifying the approaches of [6, 5] and potentially leading to new results and
insights.
Our article is organized as follows. The rest of the introduction collects some necessary
preliminary results. In Section 2 we define the Cartesian skeleton S(G) of a graph G, and
show that it satisfies S(H × K) = S(H)2S(K) for so-called “R-thin” graphs. We also
show that S(G) is connected provided that G is connected and non-bipartite. We briefly
indicate how the skeleton fits into existing results that prove unique prime factorization over
×, and we describe algorithms for its construction. Section 3 introduces a modification of
S(G), which we call S[G]. We show S[HK] = S[H]2S[K], and we obtain analogues of
the results in Section 2. The last section pertains to the implications of the new algorithms
for the prime factorization of graphs.
Our discussion is phrased in terms of vertex neighborhoods. The (open) neighborhood
of a vertex g ∈ V (G) is the set NG(g) = {g′ : gg′ ∈ E(G)}. (If there is a loop at g, then
g ∈ NG(g).) The closed neighborhood of g is NG[g] = NG(g) ∪ {g}. The degree of g is
deg(g) = |NG(g)|. It is an easy (and useful) fact that NH×K(h, k) = NH(h) × NK(k)
and NHK [(h, k)] = NH [h]×NK [k].
The notion of thinness is another important idea. To motivate this, we refer to Figure 1.
Notice that the only automorphism of H2K that interchanges vertices x and y is induced
by the nontrivial automorphism of the factor K. In fact, it is a general property [7, Corol-
lary 4.16] that any automorphism of a Cartesian product is generated by automorphisms
of its prime factors (and transpositions of isomorphic factors). By contrast, H × K (in
Figure 1) admits an automorphism that interchanges x and y and fixes all other vertices,
and this automorphism is not induced by any automorphism of the factors. It is precisely
the condition NH×K(x) = NH×K(y) that permits the interchange of x and y. Similarly,
in H K we have NHK [x] = NHK [y], and this permits an automorphism of H K
that interchanges x and y and is constant on all other vertices. This lack of rigidity tends
to complicate discussion of prime factorizations over × and . Consequently we define a
graph G to be R-thin if NG(x) = NG(y) implies x = y for all x, y ∈ V (G). Likewise
G is S-thin if NG[x] = NG[y] implies x = y for all x, y ∈ V (G). In discussions of
prime factorizations over × (respectively ) it is often helpful to impose the condition of
R-thinness (respectively S-thinness).
Recall [7, Corollaries 5.31 and 5.11] that H × K (respectively H  K) is R-thin
(respectively S-thin) if and only if both H and K are R-thin (respectively S-thin).
2 The Cartesian Skeleton for the Direct Product
In this section we define the Cartesian skeleton S(G) of an arbitrary graph G in Γ0 as a
certain graph having the same vertex set as G. We prove that S(G) is connected provided
G is connected and non-bipartite, and show S(H ×K) = S(H)2S(K) for R-thin graphs.
Our point of departure is the Boolean square.
Boolean Squares
The Boolean square of a graph G is the graph Gs with V (Gs) = V (G) and E(Gs) =
{xy : NG(x)∩NG(y) 6= ∅}. Thus, xy is an edge of Gs if and only if G has an x-y walk of
length two. For example, Ksn is Kn with a loop added to each vertex. We note in passing
194 Ars Math. Contemp. 2 (2009) 191–205
that the adjacency matrix of Gs is the Boolean square of the adjacency matrix of G, that is,
if G has adjacency matrix A then the matrix of Gs is obtained from A2 by replacing each
nonzero entry by 1.
Observe that if G has an x-y walk W of even length, then Gs has an x-y walk of length
|W |/2 on alternate vertices of W . It follows that Gs is connected if G is connected and
has an odd cycle. (For the presence of an odd cycle guarantees an even walk between any
two vertices of G.) On the other hand if G is connected and bipartite, then Gs has exactly
two components, and their respective vertex sets are the two partite sets of G.
Figure 2 shows three graphs H,K and H × K (solid) together with their Boolean
squares Hs,Ks and (H × K)s (dashed). Notice that (H × K)s = Hs × Ks. This is
in fact a general principle: Lemma 5.33 of [7] states that (G1 × G2 × · · · × Gk)s =
Gs1 ×Gs2 × · · · ×Gsk.
K
H
G = H ×K
x′ x
z′ z y
′ y
Figure 2: Graphs H , K and G = H ×K (solid) and their Boolean squares (dashed)
The Cartesian Skeleton
We now show how to remove strategic edges from Gs to obtain the Cartesian skeleton
S(G).
Given a factorizationG = H×K, we say that an edge (h, k)(h′, k′) ofGs is Cartesian
relative to the factorization H × K if either h = h′ and k 6= k′, or h 6= h′ and k = k′.
For example, in Figure 2 edges xz and zy of Gs are Cartesian (relative to the factorization
H × K), but edges xy and yy of Gs are not Cartesian. We now identify three intrinsic
criteria for edges ofGs that tell us if they may fail to be Cartesian relative to some factoring
of G.
1. If xy is a loop (i.e. if x = y) then xy cannot be Cartesian.
2. In Figure 2 edge xy of Gs is not Cartesian. For this edge of Gs there is a z ∈ V (G)
with NG(x) ∩NG(y) ⊂ NG(x) ∩NG(z) and NG(x) ∩NG(y) ⊂ NG(y) ∩NG(z).
3. In Figure 2 the edge x′y′ of Gs is not Cartesian. For this edge of Gs there is a
z ∈ V (G) with with NG(x′) ⊂ NG(z′) ⊂ NG(y′).
R. H. Hammack and W. Imrich: On Cartesian skeletons of graphs 195
Our aim is to remove from Gs all edges that meet one of these criteria. Observe that the
second and third criteria are somewhat interdependent. For example, NG(x) ⊂ NG(z) ⊂
NG(y) implies NG(x) ∩ NG(y) ⊂ NG(y) ∩ NG(z). Also, NG(y) ⊂ NG(z) ⊂ NG(x)
implies NG(x) ∩ NG(y) ⊂ NG(x) ∩ NG(z). This allows us to package the above three
conditions into the following definition.
Definition 2.1. An edge xy of Gs is dispensable if x = y or there exists z ∈ V (G) for
which both of the following statements hold.
1. NG(x) ∩NG(y) ⊂ NG(x) ∩NG(z) or NG(x) ⊂ NG(z)⊂ NG(y)
2. NG(y) ∩NG(x) ⊂ NG(y) ∩NG(z) or NG(y) ⊂ NG(z)⊂ NG(x).
Several comments are in order. First, in this paper the symbol⊂means proper contain-
ment, that is A ⊂ B means A ⊆ B and A 6= B. Also note that the above statements (1)
and (2) are symmetric in x and y. We often rely on the following remark.
Remark 2.2. We reiterate and emphasize the following.
• Condition N(x) ⊂ N(z) ⊂ N(y) in (1) implies N(y) ∩ N(x) ⊂ N(y) ∩ N(z) in
(2).
• Condition N(y) ⊂ N(z) ⊂ N(x) in (2) implies N(x) ∩ N(y) ⊂ N(x) ∩ N(z) in
(1).
• Thus non-loop edge xy is dispensable if and only if N(x) ⊂ N(z) ⊂ N(y) or
N(y) ⊂ N(z)⊂ N(x), or both N(x)∩N(y) ⊂ N(x)∩N(z) and N(y)∩N(x) ⊂
N(y) ∩N(z).
• Furthermore, if xy is not dispensable, then statementsN(x)∩N(y) ⊂ N(x)∩N(z)
and N(y) ∩N(x) ⊂ N(y) ∩N(z) cannot both be true.
Definition 2.3. The Cartesian skeleton of a graph G is the graph S(G) obtained from
Gs by removing all dispensable edges. To be specific, if G is a graph, let D(Gs) be
the set of dispensable edges of Gs. The Cartesian skeleton of G is the graph S(G) with
V (S(G)) = V (Gs) and E(S(G)) = E(Gs)−D(Gs).
Figure 3 is the same as Figure 1, except all dispensable edges ofHs,Ks and (H×K)s
are deleted. Thus the remaining dashed edges are S(H), S(K) and S(H ×K). Note that
although S(G) was defined without regard to the factorizationG = H×K, we nonetheless
have S(H ×K) = S(H)2S(K). The following lemma and proposition show this always
holds.
The proofs make frequent use of the equation
NG(h, k) ∩NG(h′, k′) = (NH(h) ∩NH(h′))× (NK(k) ∩NK(k′)),
which follows from NG(h, k) = NH(h)×NK(k) and simple set theory.
Lemma 2.4. If G is an R-thin graph with an arbitrary factorization G = H × K, then
every edge of S(G) is Cartesian with respect to this factorization.
196 Ars Math. Contemp. 2 (2009) 191–205
K
H
G = H ×K
Figure 3: Graphs H , K and H ×K (solid) and their Cartesian skeletons (dashed)
Proof. We show that any non-Cartesian edge of Gs is dispensible. Suppose that the edge
(h, k)(h′, k′) of Gs is not Cartesian. If it is a loop, then it is automatically dispensable. We
therefore assume h 6= h′ and k 6= k′. Observe:
NG(h, k) ∩NG(h′, k′) =
(
NH(h) ∩NH(h′)
)
×
(
NK(k) ∩NK(k′)
)
⊆ NH(h)×
(
NH(k) ∩NH(k′)
)
= NG(h, k) ∩NG(h, k′)
NG(h′, k′) ∩NG(h, k) =
(
NH(h′) ∩NH(h)
)
×
(
NK(k′) ∩NK(k)
)
⊆
(
NH(h′) ∩NH(h)
)
×NK(k′)
= NG(h′, k′) ∩NG(h, k′)
If both the above inclusions are proper, then (h, k)(h′, k′) is dispensable, and we are done.
Otherwise at least one inclusion is actually equality, and we getNH(h)∩NH(h′) =NH(h)
in the first case orNK(k)∩NK(k′) = NK(k′) in the second. From this,NH(h) ⊆ NH(h′)
or NK(k′) ⊆ NK(k), and by R-thinness
NH(h) ⊂ NH(h′) or NK(k′) ⊂ NK(k). (2.1)
Repeating the above argument but interchanging h with h′, and k with k′, we get that
either (h, k)(h′, k′) is dispensable (in which case we are done), or
NH(h′) ⊂ NH(h) or NK(k) ⊂ NK(k′). (2.2)
From inclusions (2.1) and (2.2) we see NK(h) ⊂ NK(h′) and NH(k) ⊂ NH(k′), or
NK(k′) ⊂ NK(k) and NH(h′) ⊂ NH(h). The first case gives
NH(h)×NK(k) ⊂ NH(h)×NK(k′) ⊂ NH(h′)×NK(k′)
which isNG(h, k) ⊂ NG(h, k′) ⊂ NG(h′, k′), so (h, k)(h′, k′) is dispensable. The second
case yields NG(h′, k′) ⊂ NG(h, k′) ⊂ NG(h, k), and again (h, k)(h′, k′) is dispensable.
R. H. Hammack and W. Imrich: On Cartesian skeletons of graphs 197
Proposition 2.5. If H , K are R-thin graphs without isolated vertices, then S(H ×K) =
S(H)2S(K).
Proof. Since the lemma states that all non-Cartesian edges of Gs are dispensable we can
restrict attention to the Cartesian edges of Gs. We must show that an edge (h, k)(h′, k) of
Gs is dispensable if and only if hh′ is dispensable in Hs. (By symmetry this implies that
(h, k)(h, k′) of Gs is dispensable if and only if kk′ is dispensable.)
Suppose hh′ is dispensable in Hs. Then there exists an z′ in V (H) such that both of
the following conditions are satisfied.
NH(h) ∩NH(h′) ⊂ NH(h) ∩NH(z′) or NH(h) ⊂ NH(z′)⊂ NH(h′)
NH(h′) ∩NH(h) ⊂ NH(h′) ∩NH(z′) or NH(h′) ⊂ NH(z′)⊂ NH(h)
(2.3)
Since NK(k) 6= ∅ (there are no isolated vertices) we can multiply each set in (2.3) by
NK(k) on the right side and still preserve the proper inclusions. Then the observation
NH(u)×NK(v) = NH×K(u, v) shows that the dispensability conditions (1) and (2) are
satisfied for x = (h, k), y = (h′, k) and z = (z′, k).
Conversely, suppose (h, k)(h′, k) is dispensable in (H × K)s, so there is a vertex
z = (z′, z′′) in H ×K such that the dispensability conditions (1) and (2) are satisfied for
x = (h, k), y = (h′, k) and z = (z′, z′′). The various cases are considered below.
If NG(x) ⊂ NG(z) ⊂ NG(y), i.e. if NH(h) × NK(k) ⊂ NH(z′) × NK(z′′) ⊂
NH(h′) × NK(k), then NK(z′′) = NK(k). Then the fact that NK(k) 6= ∅ permits can-
cellation of the common factor NK(k), so NH(h) ⊂ NH(z′) ⊂ NH(h′), and hh′ is
dispensable. We reach the same conclusion if NG(y) ⊂ NG(z)⊂ NG(x).
Finally, suppose there is a z = (z′, z′′) with both NG(x) ∩NG(y) ⊂ NG(x) ∩NG(z)
and NG(y) ∩NG(x) ⊂ NG(y) ∩NG(z). Rewrite this as
NG(h, k) ∩NG(h′, k) ⊂ (NG(h, k) ∩NG(z′, z′′)
NG(h′, k) ∩NG(h, k) ⊂ (NG(h′, k) ∩NG(z′, z′′),
which is the same as
(NH(h) ∩NH(h′))×NK(k) ⊂ (NH(h) ∩NH(z′))× (NK(k) ∩NK(z′′))
(NH(h′) ∩NH(h))×NK(k) ⊂ (NH(h′) ∩NH(z′))× (NK(k) ∩NK(z′′)).
Given that NK(k) 6⊂ NK(k) ∩NK(z′′), the following must hold.
NH(h) ∩NH(h′) ⊂ NH(h) ∩NH(z′)
NH(h′) ∩NH(h) ⊂ NH(h′) ∩NH(z′)
Thus hh′ is dispensable.
We next consider connectivity of S(G). The following lemma is needed.
Lemma 2.6. If x, y ∈ V (G) and N(x) ⊂ N(y), then Gs has an x-y path consisting of
non-dispensable edges.
Proof. We use induction on the largest integer k for which there is a chain
N(x) ⊂ N(z1) ⊂ N(z2) ⊂ N(z3) ⊂ . . . ⊂ N(zk) ⊂ N(y). (2.4)
198 Ars Math. Contemp. 2 (2009) 191–205
Note that k is the number of intermediate subsets between N(x) and N(y), and can thus
be zero. We claim that if k = 0, then xy is a non-dispensable edge of Gs. Certainly
N(x) ⊂ N(y) implies xy ∈ E(Gs). Also there is no z withN(x)∩N(y) ⊂N(x)∩N(z),
for if there were, the condition N(x) ⊂ N(y) would yield N(x) ⊂ N(x) ∩ N(z), which
is impossible. Finally, as k = 0, there is no z for which N(x) ⊂ N(z) ⊂ N(y). It follows
that xy is a non-dispensable edge of Gs.
Suppose k > 0 and that Gs has a u-v path of non-dispensable edges whenever N(u) ⊂
N(v) and the longest chain N(u) ⊂ N(w1) ⊂ N(w2) . . . ⊂ N(v) has fewer than k
intermediate sets N(wi). Then the chain (2.4) can be broken into two maximal chains
N(x) ⊂ N(z1) and N(z1) ⊂ N(z2) ⊂ N(z3) ⊂ . . . ⊂ N(y), each with fewer than k
intermediate subsets. By the inductive hypothesis there are x-z1 and z1-y paths of non-
dispensable edges in Gs.
Proposition 2.7. Suppose G is connected.
1. If G has an odd cycle, then S(G) is connected.
2. If G is bipartite, then S(G) has two components whose respective vertex sets are the
two partite sets of G.
Proof. Observe that the statement is true if S(G) is replaced by Gs. As S(G) is just Gs
with the dispensable edges removed, we need only prove that for any dispensable edge
xy ∈ E(Gs), there is an x-y path in Gs consisting of non-dispensable edges.
For each edge xy ∈ E(Gs), define the integer
kxy = max{ |N(u) ∩N(v)| − |N(x) ∩N(y)| : u, v ∈ V (G), u 6= v}.
Notice kxy ≥ 0. (Put u = x and v = y.) If kxy = 0, then the definition of kxy implies that
there is no z for which N(x)∩N(y) ⊂ N(x)∩N(z) and N(y)∩N(x) ⊂ N(y)∩N(z).
Therefore xy is not dispensable if kxy = 0.
Take N > 0, and assume that whenever Gs has a dispensable edge xy with kxy <
N there is a x-y path in Gs composed of non-dispensable edges. Now suppose xy is
dispensable and kxy = N . If N(x) ⊂ N(y) or N(y) ⊂ N(x), then we are done, by
Lemma 2.6, so assume N(x) 6⊂ N(y) and N(y) 6⊂ N(x). As xy is dispensable, there is a
vertex z with {
N(x) ∩N(y) ⊂ N(x) ∩N(z)
N(y) ∩N(x) ⊂ N(y) ∩N(z).
This implies N(x) ∩N(z) 6= ∅ 6= N(y) ∩N(z), so xz, yz ∈ E(Gs). But it also means
|N(u) ∩N(v)| − |N(x) ∩N(z)| < |N(u) ∩N(v)| − |N(x) ∩N(y)|
for all u, v, so kxz < kxy . Similarly kzy < kxy . The induction hypothesis gurantees there
are x-z and z-y paths of non-dispensable edges in Gs.
Since S(G) is defined entirely in terms of the adjacency structure of G, we have the
following immediate consequence of the definition.
Proposition 2.8. Any isomorphism ϕ : G → H , as a map V (G) → V (H), is also an
isomorphism ϕ : S(G)→ S(H).
R. H. Hammack and W. Imrich: On Cartesian skeletons of graphs 199
Prime Factor Decompositions
We pause to briefly mention how these results tie in to the existing literature concerning
unique prime factor decompositions over the direct product. Suppose there is an isomor-
phism C × D → A × B, of R-thin connected non-bipartite graphs. By the results of
the previous section this induces an isomorphism S(C)2S(D) → S(A)2S(B). Using
unique factorization properties for the Cartesian product we can factor A = A′C2A
′
D and
B = B′C2B
′
D so that the isomorphism S(C)2S(D) → A′C2A′D2B′C2B′D has form
(c, d) 7→ (αC(c), αD(d), βC(c), βD(d)). Then, as in Lemma 5.41 of [7], we construct
a “common refinement” A × B = AC × AD × BC × BD where A = AC × AD and
B = BC ×BD and C ∼= AC ×BC and D ∼= AD ×BD. From this it follows that any con-
nected R-thin non-bipartite graph has a unique prime direct product factorization (Lemma
5.38 of [7]). It is then not difficult to show (Theorem 5.4 of [7]) that the same result holds
when we remove the condition of R-thinness.
In carrying out this procedure algorithmically, it is of course essential that S(G) can be
computed efficiently. We now turn our attention to this task.
Algorithmic Construction of S(G)
Here we describe polynomial algorithms that construct S(G). For this we use an adjacency
list data structure for G. Fix an indexing V (G) = {g1, g2, . . . , gn}. Represent G as a table
with n rows indexed by the vertices g1, g2, . . . , gn. Row i contains a list of the neighbors
of gi. This is illustrated in Figure 4.
g1 g2
g4 g3
vertex neighbors
g1 g2, g4
g2 g1, g3, g4
g3 g2, g4
g4 g1, g2, g3
Figure 4: Adjacency list representation of G
If we wanted to check whether gj ∈ NG(gi), in constant time, then we could use an
adjacency matrix. However, this would require n2 space. We now show how to use a
trick from [2, Exercise 12.1-4] to check that gj ∈ NG(gi) in constant time, after some
preprocessing of O(deg(gi)) time and O(n) space.
First form a reference vector ci of length n, where every ci(k) is an uninitialized pointer.
Next form a vector `i of length deg(gi), where every entry is a pointer. For each gk in the
adjacency list for gi, do the following. If gk is the pth vertex on the adjacency list for gi, set
ci(k) to point to `i(p), and set `i(p) to point back to ci(k). Then gj ∈ N(gi) if and only
if ci(j) points to a pointer in `i that points back to ci(j). This can be checked in constant
time, while the effort to create ci and `i takes O(deg(gi)) time and O(n) space.
For x = gi we will also write cx and `x instead of ci and `i.
The next two remarks are central ideas in our algorithms.
Remark 2.9. Once ci and `i have been created and linked, we can form a list representation
of any intersectionN(gi)∩N(gj) inO(deg(gj)) time as follows. Begin with an empty list
I . Then for each x ∈ N(gj) check whether x ∈ N(gi), and if so, then append it to I .
200 Ars Math. Contemp. 2 (2009) 191–205
Remark 2.10. IfX and Y are finite sets, thenX ⊂ Y means |X| = |X∩Y | and |X| < |Y |.
For instance, N(x) ⊂ N(z) provided |N(x)| = |N(x) ∩ N(z)| and |N(x)| < |N(z)|.
Similarly N(x) ∩N(y) ⊂ N(x) ∩N(z) if |N(x) ∩N(y)| = |N(x) ∩N(y) ∩N(z)| and
|N(x) ∩N(y)| < |N(x) ∩N(z)|.
Thus we can decide whether an edge xy meets conditions (1) and (2) for dispensability
(in Definition 2.1) by making such comparisons among numbers |N(x)|, |N(y)|, |N(z)|,
|N(x) ∩N(y)|, |N(x) ∩N(z)|, |N(y) ∩N(z)|, and |N(x) ∩N(y) ∩N(z)|.
Proposition 2.11. Given an edge xy of Gs together with the reference vectors cx, `x and
cy , `y , we can check the validity of dispensability conditions (1) and (2) for any vertex
z ∈ V (G)− {x, y} in O(deg(z)) time.
Proof. We can assume that z 6= y and compute the following sets and numbers, using cx,
`x and cy , `y whenever appropriate:
(i) |NG(z)|
(ii) NG(x) ∩NG(z) and |NG(x) ∩NG(z)|
(iii) NG(y) ∩NG(z) and |NG(y) ∩NG(z)|
(iv) |NG(x) ∩NG(y) ∩NG(z)|
By comparing the cardinalities of the intersections computed above, we check if conditions
(1) and (2) from Definition 1 hold for the dispensability of xy. (See Remark 2.10.) All
computations can be executed in O(deg(z)) time.
We will present two algorithms for the computation of S(G), both based on the above
remarks. The first considers all triples of distinct vertices x, y, z.
Algorithm 2.12.
Input: Adjacency list representation for graph G with n vertices.
Output: Adjacency list representation for S(G).
1 For all pairs of distinct vertices x,y of G do:
1.1 Compute cx, `x, cy , `y and check whether xy ∈ Gs. If not, then continue with
the next pair x, y.
1.2 For all z ∈ V (G)− {x, y} check the validity of the dispensability conditions.
1.3 If the dispensability conditions fail for every z, add xy to the adjacency list of
S(G).
2 Return the adjacency list representation for S(G).
Proposition 2.13. Given an input graph G of size m and order n, the time complexity of
Algorithm 2.12 to compute S(G) is O(mn2). The space complexity is determined by the
size of the output, that is, the number of edges in S(G). It is between O(n) and O(n2).
Proof. Step 1.1 takes O(n) time. By Proposition 2.11, Step 1.2 is O(deg(z)) for every z,
contributing to a total of
∑
z∈GO(deg(z)) = O(m) time. Step 1.3 takes constant time.
Since we have to perform Steps 1.1–1.3 at most n2 times, we arrive at the asserted time
complexity.
R. H. Hammack and W. Imrich: On Cartesian skeletons of graphs 201
In the above algorithm we took all pairs x, y and checked in Step 1.1 whether they were
in E(Gs). For the pair x, z the check occurs in Step 1.2.
The next algorithm makes use of the fact that conditions (1) and (2) for dispensability
in Definition 2.1 can hold only if y and z are both at distance two from x. (We must have
dG(x, y) = 2 for xy ∈ E(Gs), and dG(x, z) 6= 2 implies NG(x) ∩ NG(z) = ∅, whence
none of the conditions hold. In fact, by condition (2), there must be a neighbor of x, say
y′, that is adjacent to both y and z.) The algorithm let y and z run through the sets of
neighbors of neighbors of x. To reach all vertices y of distance 2 from x we thus consider
all neighbors y′ of x and then all neighbors y of the y′. Since it may be possible to reach
y from x on many distinct paths of length 2, and since we do not know all paths a priori,
the complexity of this method may be high. However, if ∆3 < n2, then it is better than
O(mn2), as we shall see.
Note that we already observed that we can assume the existence of a y′ ∈ N(x) that is
a neighbor of both y and z.
Algorithm 2.14.
Input: Adjacency list representation for graph G with n vertices.
Output: Adjacency list representation for S(G).
1 For each x ∈ V (G) do:
1.1 Compute cx, `x and |NG(x)|.
1.2 For every y′ ∈ NG(x) do:
1.2.1 For all y ∈ NG(y′)− {x} do:
1.2.1.1 Compute cy , `y and |NG(y)|.
1.2.1.2 For all z ∈ NG(y′)− {x, y} do:
1.2.1.2.1 Check the dispensability conditions (1) and (2).
1.2.1.3 If dispensability conditions fail for every z, add xy to the adja-
cency list of S(G).
2 Return the adjacency list representation for S(G).
Proposition 2.15. Given an input graph G of size m, order n and maximum degree ∆, the
time complexity of Algorithm 2.14 to compute S(G) is O(m∆3). The space complexity is
between O(n) and O(n2).
Proof. We have loops for x, y′, y, z, and show first that the complexity is given by the
expression
∑
x∈V (G)
O(|N(x)|) + ∑
y′∈N(x)
∑
y∈N(y′)
O(|N(y)|) +
 ∑
z∈N(y′)
O(|N(z)|)
+O(1)
 .
The sum over x ∈ V (G) stands for the Loop 1 in the algorithm, and the term O(|N(x)|)
expresses the contribution of Step 1.1.
The next step in the x-loop is 1.2. It is a sum over all neighbors of x. For every such
neighbor y′ we have to execute 1.2.1. It is a loop for all y ∈ N(y′). Every instance
202 Ars Math. Contemp. 2 (2009) 191–205
consists of three subinstances. The cost for 1.2.1.1 is O(|N(y)|), the one for 1.2.1.3 is
O(1), whereas 1.2.1.2 is a sum over z ∈ N(y′), every instance contributing a cost of
O(|N(z)|).
To evaluate this expression, note that the term 1.2.1.2 is nested in all loops and has the
largest contribution to the complexity. It therefore suffices to evaluate just the expression∑
x∈V (G)
∑
y′∈N(x)
∑
y∈N(y′)
∑
z∈N(y′)
O(|N(z)|).
Clearly
∑
y∈N(y′)
∑
z∈N(y′)O(|N(z)|) = O(∆3). Thus the total value is∑
x∈V (G)
∑
y′∈N(x)
O(∆3) = O(∆3)
∑
x∈V (G)
∑
y′∈N(x)
1 = O(∆3)
∑
x∈V (G)
|N(x)| = O(∆3)2m.
Note that O(m∆3) is a better bound than O(mn2) when ∆3 < n2, and that m∆3 can be
close to n for sparse graphs, say direct products of cycles or of cubic graphs.
3 The Cartesian Skeleton for the Strong Product
We now describe a variation on S(G), which we denote as S[G]. This modified skeleton
is a subgraph of G (not of Gs) having the property S[H K] = S[H]2S[K]. We define
it almost exactly as we defined S(G), except that we use closed neighborhoods instead of
open neighborhoods, and it is a subgraph of G rather than Gs.
We say an edge xy of a graph G ∈ Γ is dispensable if there exists z ∈ V (G) for which
both of the following statements hold.
(1-strong) NG[x] ∩NG[y] ⊂ NG[x] ∩NG[z] or NG[x] ⊂ NG[z] ⊂ NG[y]
(2-strong) NG[y] ∩NG[x] ⊂ NG[y] ∩NG[z] or NG[y] ⊂ NG[z] ⊂ NG[x].
The closed Cartesian skeleton of G is the graph S[G] obtained from G by removing all
dispensable edges.
From here we easily obtain analogues of Lemmas 2.4 and 2.6 and Propositions 2.5 and
2.7. In the proofs one simply replaces open neighborhoods with closed neighborhoods.
We use NHK [(h, k)] = N [h] × N [k] instead of NH×K(h, k) = N(h) × N(k). We
also replace the condition (N(x) = N(y)) =⇒ (x = y) for R-thinness with with the
condition (N [x] = N [y]) =⇒ (x = y) for S-thinness. Reasoning exactly as we did for
S(G) we obtain the following results for S[G]. (The only substantial difference is that for
connectivity we no longer need G to be non-bipartite, as S[G] is a subgraph of G, not of
Gs. We can also remove the condition that G have no isolated vertices, since N [x] 6= ∅,
even if x is isolated.)
Proposition 3.1. IfG is connected, then S[G] is connected. Also, S[HK] = S[H]2S[K]
for S-thin graphs.
We now adapt Algorithm 2.12 to S[G]. Note that the complexities of computing inter-
sections of closed neighborhoods are the same as those for open neighborhoods. We use
the same notation ci and `i for the reference vectors for closed neighborhoods.
R. H. Hammack and W. Imrich: On Cartesian skeletons of graphs 203
We remark that conditions (1-strong) and (2-strong) for dispensability can hold only if
y and z are both inN [x]. (We must have y ∈ N(x) in order that xy ∈ E(G), and z /∈ N [x]
implies N [x]∩N [y] 6⊂ N [x]∩N [z], whence none of the conditions hold.) In other words,
the dispensability conditions can hold only if x, y and z induce a triangle in G. Thus in
checking for dispensability of xy, the algorithm needs to consider only those z in N [x].
We will also make use of the analog of Proposition 2.11 for strong products. Its validity
is obvious by the above remarks.
Proposition 3.2. Given distinct vertices x,y in V (G) together with reference vectors cx, `x
and cy , `y , we can check the validity of dispensability conditions (1-strong) and (2-strong)
for any vertex z ∈ V (G)− {x, y} in O(deg(z)) time.
Algorithm 3.3.
Input: Adjacency list representation for graph G with n vertices.
Output: Adjacency list representation for S[G].
1 For each edge xy ∈ E(G) do:
1.1 Compute cx, `x, cy , and `y .
1.2 For each z ∈ N(x) check the validity of the dispensability conditions.
1.3 If these conditions fail for all z, add xy to the adjacency list of S[G].
2 Return the adjacency list representation for S[G].
Proposition 3.4. If graph G has m edges, and maximum degree ∆, then the complexity of
using Algorithm 3.3 to compute S[G] is the minimum of O(m2) and O(m∆2).
Proof. Every instance of Loop 1 has three subinstances. The first takes O(∆) time, and
the last constant time. We will bound the second in two ways.
On one hand, for every z the cost of checking dispensability is O(|N(z)|). Since z ∈
N(x) and N(x) ⊆ V (G), the time for Loop 1.2 is bounded by
∑
z∈V (G)O(|N(z)|) =
O(m). Hence every instance of Loop 1 takes O(∆) +O(m) +O(1) time. Since there are
m edges we arrive at a total complexity of O(m2).
On the other hand, the z are among the at most ∆ neighbors of x, so the time needed
for every z is bounded by O(|N(z)|) = O(∆). This yields the bound of O(∆2) for 1.2,
and a total of O(m∆2).
A Bound Involving Arboricity
The arboricity a(G) of a graph G is the minimum number of forests into which its edges
can be partitioned. It is a measure of density of G. By a theorem of Nash-Williams [11, 7]
the arboricity equals
a(G) = max
H⊆G
⌈
|E(H)|
|V (H)| − 1
⌉
,
where the maximum is taken over all nontrivial graphs H ⊆ G.
204 Ars Math. Contemp. 2 (2009) 191–205
Observe that ∆ is an upper bound of a(G) for graphs with at least one edge. Clearly the
arboricity of a tree T is 1, whereas its maximum degree ∆ can be as large as |V (T )| − 1.
Hence a(G) can be significantly smaller than ∆.
In the remainder of the paper we will present a variant of Algorithm 3.3 for the com-
putation of S[G], having complexity O(ma(G) ∆). In order to do this we make use of
a result of Chiba and Nishizeki [1, 7], which states that all triangles of a graph G can be
listed in O(ma(G)) time and space. We also use the fact—noted above—that dispensabil-
ity conditions (1-strong) and (2-strong) can hold only if x, y, z lie on a triangle.
Algorithm 3.5.
Input: Adjacency list representation for graph G with n vertices.
Output: Adjacency list representation for S[G].
1 Compute all triangles of G with the algorithm of Chiba and Nishizeki.
2 Initialize an empty list t(e) for every edge e ∈ E(G).
3 Scan all triangles x1x2x3.
3.1 For every edge e = xixj of this triangle add the third vertex xk to t(e).
4 For each edge xy ∈ E(G) do:
4.1 Compute cx, `x, cy , and `y .
4.2 For each z ∈ t(xy) check the validity of the dispensability conditions.
4.3 If the dispensability condition fails for every z, add xy to the adjacency list of
S[G].
5 Return the adjacency list representation for S[G].
A complexity analysis along the lines of the previous ones yields the following propo-
sition.
Proposition 3.6. If graph G has m edges, arboricity a(G), and maximum degree ∆, then
S[G] can be computed in O(ma(G) ∆) time and O(ma(G)) space.
4 The role of the Cartesian skeleton for prime factorization
In this section we indicate that the complexity of the computation of S(G), respectively
S[G], determines the complexity of the prime factorization of graphs with respect to the
direct, respectively the strong product. No formal proofs are given here.
As has already been pointed out in Section 2, the first step in the prime factorization of
a graph is the computation of GR = G/R, respectively GS = G/S. This can actually be
done in linear time, but even more mundane direct algorithms will not be more complex
than the respective algorithms for the computation of the skeletons.
Then S(GR), respectively S[GS ], is decomposed into its prime factors with respect to
the Cartesian product. Since the effort to find this factorization is linear in the number of
edges of the graph to be factored we remain within the time limit.
R. H. Hammack and W. Imrich: On Cartesian skeletons of graphs 205
Now comes a more complex stage. Since the number of Cartesian factors of S(GR),
respectively S[GS ], can be larger than the number of direct, respectively strong, factors, it
may be necessary to combine several Cartesian factors to get the prime direct, respectively
strong, factors. In [7] all combinations of the prime factors of the Cartesian skeleton are
computed for this purpose. Since the number of prime factors of a graph on n vertices is
at most log2 n the number of combinations is bounded by 2log2 n = n. The cost of testing
every combination is the number of edges times the number of factors in GR, resp. GS .
This leads to a complexity of O(mn log2 n) for this step, which may be larger than the
complexity bounds of our algorithms involving ∆.
Luckily one can also bound the number of factors of the Cartesian skeleton by log2 ∆2
in the case of the direct product and by log2 ∆ in the case of the strong one, but this needs
some argument.
From these bounds one can then obtain the complexities O(n∆2 log2 ∆), respectively
O(m∆ log2 ∆), for finding the prime factors of GR, respectively GS , from the prime fac-
torizations of the Cartesian skeletons.
Finally, once the prime factorizations of GR, respectively GS , have been found simple
arithmetic suffices to find the factorizations of G.
References
[1] N. Chiba and T. Nishizeki, Arboricity and subgraph listing algorithms, SIAM J. Comput. 14
(1985), 210–223.
[2] T. H. Cormen, C. E. Leiserson and R. L. Rivest, Introduction to Algorithms, McGraw Hill, New
York, 1990.
[3] 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.
[4] J. Feigenbaum, J. Hershberger and A. A. Schäffer, A polynomial time algorithm for finding the
prime factors of Cartesian-product graphs, Discrete Appl. Math. 12 (1985), 123–138.
[5] J. Feigenbaum and A. A. Schäffer, Finding prime factors of strong direct product graphs in
polynomial time, Discrete Math. 109 (1992), 77–102.
[6] W. Imrich, Factoring cardinal product graphs in polynomial time, Discrete Math. 192 (1998),
119–144.
[7] W. Imrich and S. Klavžar, Product Graphs; Structure and Recognition, Wiley Interscience
Series in Discrete Mathematics and Optimization, New York, 2000.
[8] W. Imrich, S. Klavžar and D. Rall, Topics in Graph Theory: Graphs and Their Cartesian
Product, A. K. Peters Ltd., Wellesley, MA, 2008.
[9] W. Imrich and I. Peterin, Recognizing Cartesian products in linear time. Discrete Math. 307
(2007), 472–483.
[10] R. McKenzie, Cardinal multiplication of structures with a reflexive relation, Fund. Math. 70
(1971), 59–101.
[11] C. St. J. A. Nash-Williams, Decomposition of finite graphs into forests, J. London Math. Soc.
39 (1964), 12.
[12] G. Sabidussi, Graph multiplication, Math Z. 72 (1960), 446–457.
[13] V. G. Vizing, The Cartesian product of graphs (Russian), Vyčisl. Sistemy 9 (1963), 30–43.