Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 3 (2010) 193–199
The inner power of a graph
Richard H. Hammack
Department of Mathematics and Applied Mathematics
Virginia Commonwealth University, Richmond, VA 23284-2014, USA
Neal D. Livesay
Department of Mathematics, Louisiana State University
Baton Rouge, LA 70803-4918, USA
Received 2 June 2010, accepted 1 October 2010, published online 10 November 2010
Abstract
We define a new graph operation called the kth inner power. The construction—which
is somewhat analogous to the kth power with respect to the direct product—seems to lend
itself nicely to certain questions concerning cancellation over the direct product. We prove
several results about bipartiteness and connectedness of inner powers, and we prove that the
inner power distributes over the direct product. We explore a potential connection between
inner powers and the problem of cancellation over the direct product.
Keywords: Graph producs, graph operations, cancellation in graph products.
Math. Subj. Class.: 05C76, 05C99
1 Introduction
Our purpose is to define a new graph operation which we call an inner power. The article
is organized as follows. The introduction recalls some relevant notation and lexicon; the
second section defines the inner power and proves some of its elementary properties. In
the final section we explore potential applications of the inner power to the problem of
cancellation over the direct product.
We recall some standard definitions to fix the notation. Any graph G = (V (G), E(G))
in this paper is finite and may have loops, but not multiple edges. Edges are denoted xy,
where x, y ∈ V (G). A loop at x is denoted xx. The cycle Cn is the graph with vertices
0, 1, . . . , n− 1, where i is adjacent to i+ 1 (with arithmetic done modulo n). The path Pn
has vertex set 1, . . . , n, with i adjacent to i+ 1 for 1 ≤ i < n. We use the notation G ⊆ H
E-mail addresses: rhammack@vcu.edu (Richard H. Hammack), nlives1@lsu.edu (Neal D. Livesay)
Copyright c© 2010 DMFA Slovenije
194 Ars Math. Contemp. 3 (2010) 193–199
to indicate that G is a subgraph of H . A walk in G is a sequence of vertices x1x2 . . . xn
in G for which xixi+1 ∈ E(G) for each 1 ≤ i < n. The walk is closed if x1 = xn.
A homomorphism from a graph G to a graph H is a map ϕ : V (G) → V (H) for which
xy ∈ E(G) implies ϕ(x)ϕ(y) ∈ E(H).
The direct product G × H is the graph with vertex set V (G) × V (H) and for which
(x, y)(x′, y′) is an edge precisely if xx′ ∈ E(G) and yy′ ∈ E(H). Figure 1 shows a direct
product G × H . For clarity, the factors G and H are drawn below and to the left of the
product.
G
G×HH
Figure 1: A direct product G×H
The direct product can also be defined on k factors. Given graphs G1, G2, . . . , Gk, the
product G1×G2×· · ·×Gk has as vertices the k-tuples (x1, x2, . . . , xk), with xi ∈ V (Gi)
for 1 ≤ i ≤ k. Vertices (x1, x2, . . . , xk) and (y1, y2, . . . , yk) are adjacent provided that
xiyi ∈ E(Gi) for 1 ≤ i ≤ k. The kth direct power of a graph G is the product Gk =
G×G× · · · ×G of G with itself k times.
See Imrich and Klavžar [2] for a survey of the direct product.
2 The inner power
We now introduce our main construction. Given a graph G, and a positive integer k, the
kth inner power of G is the graph G(k) defined as follows, where arithmetic on the indices
is done modulo k.
V (G(k)) = {(x0, x1, . . . , xk−1) : xi ∈ V (G) for 0 ≤ i < k}
E(G(k)) = {(x0, x1, . . . , xk−1)(y0, y1, . . . , yk−1) : xiyi±1 ∈ E(G) for 0 ≤ i < k}
Notice that if k = 2, then (x, y)(x′, y′) is an edge of G(2) if and only if xy′ ∈ E(G)
and yx′ ∈ E(G). Figure 2 shows two examples. The left-hand side shows K(2)2 , while the
right-hand side shows the second inner power of the graph G consisting of two loops.
( )
(2)
=
(0, 1) (1, 1)
(0, 0) (1, 0)
0
1
( )
(2)
=
(0, 1) (1, 1)
(0, 0) (1, 0)
0
1
Figure 2: The inner powers K(2)2 and G
(2), where G consists of two loops.
R. H. Hammack and N. D. Livesay: The inner power of a graph 195
Figure 3 shows some more elaborate examples, namely P (2)3 and C
(2)
3 , where, for con-
venience, the vertices are labeled as xy rather than (x, y). This figure illustrates a general
principle that follows immediately from the definition of the inner power: If G ⊆ H , then
G(k) ⊆ H(k). Figure 4 shows the inner power C(3)3 . Notice that in general the diagonal
map x 7→ (x, x, . . . , x) is an embedding of G into G(k).
( )
(2)
=
0
1
2
00
1
1
22
12
02
20
10
01
21
( )
(2)
=
0
1
2
00
1
1
22
12
02
20
10
01
21
Figure 3: The inner powers C(2)3 and P
(2)
3 . Note G ⊆ H implies G(k) ⊆ H(k).
We note in passing that C(2)3 and C
(3)
3 happen to coincide with the coloring graphs
C3(K2) and C3(C3) (see Section 8.2 of [2]), suggesting a possible (and entirely unexplored)
connection to graph colorings.
We now collect some properties of inner powers, beginning with a criterion that char-
acterizes the presence of a loop in the inner power. The proof is an immediate consequence
of the definitions, and is therefore omitted.
Proposition 2.1. The inner power G(k) has a loop at (x0, x1, . . . , xk−1) if and only if the
sequence x0x1 . . . xk−1x0 is a closed walk in G.
Thus if k is even and G has an edge xy, then G(k) has a loop at (x, y, x, y, . . . , x, y).
Consequently an even inner power of a nontrivial graph is never bipartite. But we do have
the following.
Proposition 2.2. An inner power G(k) is bipartite if and only if G is bipartite and k is odd.
Proof. If G(k) has no odd cycles, then as G embeds in G(k), it follows that G has no odd
cycles.
196 Ars Math. Contemp. 3 (2010) 193–199
( )
(3)
=
0
1
2
00
0
1
1
1
22
2
0
1
2
1
2
0
201
02
1 102
210
112
121
211
00
2
02
0
20
0
220
202
022
110
101
011
0
0
1
0
1
0
1
0
0
2
2
1
2
1
2
1
2
2
Figure 4: The inner power C(3)3 .
Conversely, suppose k is an odd integer and G is a bipartite graph with partite sets
X and Y . Consider an arbitrary edge (x0, x1, . . . , xk−1)(y0, y1, . . . , yk−1) ∈ E(G(k)).
Suppose, without loss of generality, that x0 ∈ X . Then since x0y1 ∈ E(G), we have
y1 ∈ Y . In turn, since y1x2 ∈ E(G), we have x2 ∈ X . Similarly, y3 ∈ Y , x4 ∈
X , and so on. Because k is odd we infer (x0, x1, . . . , xk−1) ∈ X × X × · · · × X and
(y0, y1, . . . , yk−1) ∈ Y × Y × · · · × Y . It follows that any edge of G(k) has one endpoint
in the set X ×X × · · · ×X and the other endpoint in V (G(k)) \X ×X × · · · ×X . Thus
G(k) is bipartite.
Recall (Theorem 5.5 of [2]) that a direct product G×H of nontrivial graphs is connected
if and only if both G and H are connected and one of them has an odd cycle. Consequently
a direct power Gk is connected if and only if G is connected and non-bipartite. By contrast,
Figure 4 shows that inner powers of connected non-bipartite graphs may be disconnected.
However (as the next result indicates) for k = 2 the criteria for connectedness of the inner
power is exactly the same as for the direct power.
Proposition 2.3. An inner power G(2) is connected if and only if G is connected and has
an odd cycle.
Proof. Suppose G(2) is connected. Then for any two vertices x, y ∈ E(G), there is a path
from (x, y) to (y, y) in G(2). Denote this path as
(x, y)(x1, y1)(x2, y2)(x3, y3) . . . (xn, yn)(y, y).
By the definition of the inner power, xx1y2x3y4 . . . y is a walk in G from x to y. Thus G
is connected.
Conversely, suppose that G is connected and contains an odd cycle. Let (a, b), (c, d) ∈
V (G(2)). Then G has an even walk from a to c. (By traversing an odd cycle, if necessary.)
R. H. Hammack and N. D. Livesay: The inner power of a graph 197
Similarly, G has an even walk from b to d. What is more, we may assume these walks have
the same length, by alternating back and forth along a final edge, if necessary. Therefore G
has walks ax0x1x2 . . . x2nc and by0y1y2 . . . y2nd. This gives rise to the walk
(a, b)(y0, x0)(x1, y1)(y2, x2)(x3, y3) . . . (y2n, x2n)(c, d)
in G(2). Thus G(2) is connected.
Connectedness for powers higher than 2 is much more subtle issue, as the next result
indicates.
Proposition 2.4. Suppose k > 2. Then there is a walk in G(k) joining (x0, x1, . . . , xk−1)
to (y0, y1, . . . , yk−1) if and only if for some n there is a homomorphism ϕ : Pn×Ck → G,
where ϕ(1, i) = xi and ϕ(n, i) = yi for each index i.
Proof. Suppose there is such a homomorphism. By the homomorphism property of ϕ, as
well as the definitions of the direct product and the inner power, it follows that for each
1 ≤ ` < n the vertex
(
ϕ(`, 0), ϕ(`, 1), . . . , ϕ(`, k − 1)
)
is adjacent to(
ϕ(`+ 1, 0), ϕ(`+ 1, 1), . . . , ϕ(`+ 1, k − 1)
)
in G(k). Therefore G(k) has a walk from (x0, x1, . . . , xk−1) to (y0, y1, . . . , yk−1).
Conversely, suppose G(k) has a path from (x0, x1, . . . , xk−1) to (y0, y1, . . . , yk−1).
Write this path as(
v10 , v
1
1 , . . . , v
1
k−1
)(
v20 , v
2
1 , . . . , v
2
k−1
)(
v30 , v
3
1 , . . . , v
3
k−1
)
. . .
(
vn0 , v
n
1 , . . . , v
n
k−1
)
,
where the left-most vertex is (x0, x1, . . . , xk−1) and the right-most is (y0, y1, . . . , yk−1).
Define ϕ(`, i) = v`i . One checks easily that this is the required homomorphism.
Proposition 2.4 yields the following corollary.
Corollary 2.5. The inner power G(k) is connected if and only if for any two k-tuples
(x0, x1, . . . , xk−1) and (y0, y1, . . . , yk−1) of vertices of G, there exists a homomorphism
ϕ : Pn × Ck → G, where ϕ(1, i) = xi and ϕ(n, i) = yi.
Finally, we prove that the inner power distributes over the direct product.
Proposition 2.6. For any graphs G and H , it follows that (G×H)(k) ∼= G(k) ×H(k).
Proof. Consider the bijection ϕ : V
(
(G×H)(k)
)
→ V
(
G(k) ×H(k)
)
, where
ϕ(((x0, y0), (x1, y1), ..., (xk−1, yk−1))) = ((x0, x1, ..., xk−1), (y0, y1, ..., yk−1)).
This is an isomorphism because
((x0, y0), ..., (xk−1, yk−1))((u0, v0), ..., (uk−1, vk−1)) ∈ E
(
(G×H)(k)
)
,
⇐⇒ (xi, yi)(ui±1, vi±1) ∈ E(G×H) for each index i,
⇐⇒ xiui±1 ∈ E(G) and yivi±1 ∈ E(H) for each index i,
⇐⇒ (x0, x1, . . . , xk−1)(u0, u1, . . . , uk−1) ∈ E(G(k)) and
(y0, y1, . . . , yk−1)(v0, v1, . . . , vk−1) ∈ E(H(k))
⇐⇒
(
(x0, . . . , xk−1), (y0, . . . , yk−1)
)(
(u0, . . . , uk−1), (v0, . . . , vk−1)
)
∈
E
(
G(k) ×H(k)
)
.
198 Ars Math. Contemp. 3 (2010) 193–199
3 Cancellation
The cancellation problem for the direct product involves the determination of the conditions
under which G × K ∼= H × K implies G ∼= H . We now review some classic results
involving cancellation, and we note a potential application of inner powers to cancellation.
Given graphs G and H , denote by hom(G,H) the number of homomorphisms from G
to H . The following theorem by Lovász is proved in [3] and [1]. (Actually, the cited proofs
are for digraphs, but the arguments work equally well for graphs.)
Theorem 3.1. If G and H are graphs, then G∼=H if and only if hom(X,A)=hom(X,B)
for every graph X .
Lovász [3] also noted the easily-proved identity
hom(X,A×B) = hom(X,A) · hom(X,B). (3.1)
From this he deduced the following corollaries. (The first one involves the direct power of
a graph, not the inner power.)
Corollary 3.2. If Gk ∼= Hk, then G ∼= H .
Proof. Suppose Gk ∼= Hk. Let X be any graph. Then hom(X,Gk) = hom(X,Hk), and
Equation (3.1) yields hom(X,G)k = hom(X,H)k. Thus hom(X,G) = hom(X,H), so
G ∼= H by Theorem 3.1.
Corollary 3.3. If G×K ∼= H ×K and K has a loop, then G ∼= H .
Proof. Suppose G×K ∼= H×K. For any graph X hom(X,G×K) = hom(X,H×K),
and Equation (3.1) yields
hom(X,G) · hom(X,K) = hom(X,H) · hom(X,K).
Now, hom(X,K) 6= 0 because the constant map sending V (X) to a vertex with a loop is
a homomorphism. Thus hom(X,G) = hom(X,H), so G ∼= H by Theorem 3.1.
Lovász [3] also proves the following generalization of Corollary 3.3: If G×K ∼= H×K
and K has an odd cycle, then G ∼= H . His proof, involving a theory of k-partite structures,
is quite complex and (at least to our thinking) non-intuitive. In the final part of this paper
we explore the possibility that the inner power may lead to a simpler proof.
To this end, we first remark that the analogue of Corollary 3.2 does not hold for inner
powers. Indeed, Figure 2 shows that it is possible to have G(k) ∼= H(k) with G 6∼= H .
However, despite considerable effort we have found no examples of this phenomenon when
k is odd, and we are led to the following conjecture.
Conjecture 3.4. If k is odd and G(k) ∼= H(k), then G ∼= H .
We conclude by showing how the truth of the conjecture could lead to simpler proof of
Lovász’s cancellation theorem.
Proposition 3.5. Suppose Conjecture 3.4 is true. If G×K ∼= H ×K, and K has an odd
cycle, then G ∼= K.
R. H. Hammack and N. D. Livesay: The inner power of a graph 199
Proof. Suppose G ×K ∼= H ×K, and K has an odd cycle x0x1x2 . . . xk−1x0 of length
k. Then (G×K)(k) ∼= (H ×K)(k), and Proposition 2.6 yields
G(k) ×K(k) ∼= H(k) ×K(k).
Proposition 2.1 guarantees that K(k) has a loop at the vertex (x0, x1, x2, . . . , xk−1). Corol-
lary 3.3 thus gives G(k) ∼= H(k), hence G ∼= H .
References
[1] P. Hell and J. Nešetřil, Graphs and Homomorphisms, Oxford Lecture Series in Mathematics,
Oxford University Press, Oxford, 2004.
[2] W. Imrich and S. Klavžar, Product Graphs: Structure and recognition, Wiley-Interscience Series
in Discrete Mathematics and Optimization, John Wiley and Sons, New York, 2000.
[3] L. Lovász, On the cancellation law among finite relational structures, Period. Math. Hungar. 1(2)
(1971), 145–156.