Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 2 (2009) 241–262
Enumeration of I-graphs:
Burnside does it again
Marko Petkovšek
University of Ljubljana, Faculty of Mathematics and Physics
Jadranska 19, SI-1000 Ljubljana, Slovenia
Helena Zakrajšek
University of Ljubljana, Faculty of Mechanical Engineering
Aškerčeva 6, SI-1000 Ljubljana, Slovenia
Received 21 July 2009, accepted 12 November 2009, published online 17 December 2009
Abstract
We give explicit and efficiently computable formulas for the number of isomorphism
classes of I-graphs, connected I-graphs, bipartite connected I-graphs, generalized Petersen
graphs, and bipartite generalized Petersen graphs. The tool that we use is the well-known
Cauchy-Frobenius-Burnside lemma.
Keywords: I-graphs, generalized Petersen graphs, Cauchy-Frobenius-Burnside lemma, arithmetical
functions.
Math. Subj. Class.: 05A15, 05C30
1 Introduction
Recently the class of I-graphs, introduced in the Foster Census [2] as a further develop-
ment of the generalized Petersen graphs, has received considerable attention. One rea-
son for this is that bipartite I-graphs give rise to some highly symmetric configurations of
points and lines [1]. In the same paper, Boben, Pisanski and Žitnik characterized the au-
tomorphism groups of those I-graphs which are not generalized Petersen graphs, so that
together with the earlier results of Frucht, Graver and Watkins [3], the characterization of
the automorphism groups of I-graphs is now complete. Finally, Horvat, Pisanski and Žitnik
have recently shown that every I-graph has a nondegenerate unit-distance representation in
the Euclidean plane [4]. This answers the question of whether every generalized Petersen
E-mail addresses: marko.petkovsek@fmf.uni-lj.si (Marko Petkovšek), helena.zakrajsek@fs.uni-lj.si (Helena
Zakrajšek)
Copyright c© 2009 DMFA Slovenije
242 Ars Math. Contemp. 2 (2009) 241–262
graph can be drawn in the plane in such a way that all edges are represented by straight-line
segments of equal length.
As witnessed by the recent inclusion of the corresponding counting sequences in [10],
there has also been interest in the enumeration of non-isomorphic I-graphs and various of
their subclasses, such as connected I-graphs, generalized Petersen graphs, etc. However,
explicit formulas for the n-th term of these sequences seem to be unknown, with the sole
exception of the formula for the number of non-isomorphic generalized Petersen graphs
G(n, k) on 2n vertices with gcd(n, k) = 1, given quite recently by Steimle and Staton [12,
Thm. 11].
At a seminar meeting in Ljubljana in January 2009, T. Pisanski asked for a formula enu-
merating non-isomorphic I-graphs on 2n vertices. We give such a formula below in Section
2, as well as analogous formulas enumerating non-isomorphic connected I-graphs, bipartite
connected I-graphs, generalized Petersen graphs, and bipartite generalized Petersen graphs
on 2n vertices. These formulas are in closed form, and can be used for efficient compu-
tation of the number of isomorphism classes, provided that the prime factorization of n is
known.
To enumerate isomorphism classes we use the Cauchy-Frobenius lemma, also known
as Burnside’s lemma. Although very well known, this lemma is seldom applied directly,
but rather indirectly via the Redfield-Pólya enumeration theorem whose proof relies on it.
Recently, though, it has been used successfully on its own in several cases (cf. [9, 6, 7]).
For n ∈ N write Zn = {0, 1, . . . , n− 1} and Z′n = Zn \ {0, n/2}. Let n ∈ N, n ≥ 3,
and j, k ∈ Z′n. The I-graph I(n, j, k) is the graph G = (V,E) where
V = Zn × Z2,
E =
n−1⋃
i=0
{{(i, 0), (i, 1)}, {(i, 0), (i+ j, 0)}, {(i, 1), (i+ k, 1)}},
and addition is performed modulo n. Well-known special cases include the n-prism Yn =
I(n, 1, 1), the Petersen graph I(5, 1, 2), and the generalized Petersen graph G(n, k) =
I(n, 1, k), introduced by Watkins in [13].
The I-graph I(n, j, k) is a cubic graph on 2n vertices. In [1], several graph-theoretic
properties of I(n, j, k) such as connectedness, girth, being bipartite or being vertex-sym-
metric, are characterized in terms of number-theoretic properties of parameters n, j, k. An
algorithm for deciding which sets of parameter values give rise to isomorphic I-graphs is
also given there. In [5], the following result (crucial for our enumeration) is proved:
Theorem 1.1. I(n, j, k) and I(n, j′, k′) are isomorphic if and only if there exists an integer
a, relatively prime to n, such that either {j′, k′} = {aj mod n, ak mod n} or {j′, k′} =
{aj mod n,−ak mod n}.
We also rely on the following results from [1]:
Theorem 1.2. The graph I(n, j, k) is connected if and only if gcd(n, j, k) = 1.
Theorem 1.3. A connected graph I(n, j, k) is bipartite if and only if n is even and j and k
are odd.
In the rest of the paper, we use the following notation (for n ∈ N):
M. Petkovšek and H. Zakrajšek: Enumeration of I-graphs: Burnside does it again 243
I(n) = the number of isomorphism classes of I-graphs I(n, j, k)
(sequence A153846 in [10])
Ic(n) = the number of isomorphism classes of connected I-graphs
I(n, j, k) (sequence A153847 in [10])
Ibc(n) = the number of isomorphism classes of bipartite connected
I-graphs I(n, j, k)
P (n) = the number of isomorphism classes of generalized Petersen
graphs G(n, k) = I(n, 1, k) (sequence A077105 in [10])
Pb(n) = the number of isomorphism classes of bipartite generalized
Petersen graphs G(n, k) = I(n, 1, k) (sequence A107452 in [10])
Pr(n) = the number of isomorphism classes of generalized Petersen
graphs G(n, k) = I(n, 1, k) with gcd(n, k) = 1
Zn = {0, 1, . . . , n− 1} (the ring of integers modulo n)
Z∗n = {a ∈ Zn; gcd(a, n) = 1} (the group of units of Zn)
Z′n = Zn \ {0, n/2} (the set of legal values for j, k in I(n, j, k))
For k ∈ Z, we write k mod n to denote the unique r ∈ Zn such that k ≡ r (mod n).
In particular, if n is even, then
(n/2) mod 2 =
{
0, n ≡ 0 (mod 4),
1, n ≡ 2 (mod 4).
Table 1 lists the arithmetical functions that appear in the rest of the paper. The column
“OEIS id” in Table 1 gives the corresponding identifier from [10].
notation OEIS id comments
µ(n) A008683 Moebius function
τ(n) A000005 the number of divisors of n
ϕ(n) A000010 Euler’s totient function,
ϕ(n) = |{j ∈ Zn; gcd(n, j) = 1}| = |Z∗n|
J2(n) A007434 the second Jordan’s totient function,
J2(n) = |{(j, k) ∈ Zn × Zn; gcd(n, j, k) = 1}|
ω(n) A001221 the number of distinct prime factors of n
r(n) A060594 the number of square roots of 1 modulo n,
r(n) = |{a ∈ Zn; a2 ≡ 1(mod n)}|
s(n) A000089 the number of square roots of −1 modulo n,
s(n) = |{a ∈ Zn; a2 ≡ −1(mod n)}|
Table 1: Some arithmetical functions.
With the exception of ω(n) which is additive, all other functions in Table 1 are multi-
plicative. If p is a prime and k ≥ 1, we have
J2(pk) = p2k − p2k−2 =
∑
d | pk
µ
(
pk
d
)
d2,
244 Ars Math. Contemp. 2 (2009) 241–262
r(pk) =
 1, p = 2 and k = 1,2, p odd or (p = 2 and k = 2),4, p = 2 and k ≥ 3,
s(pk) =
 0, p ≡ 3 (mod 4) or (p = 2 and k ≥ 2),1, p = 2 and k = 1,2, p ≡ 1 (mod 4),
hence
J2(n) = n2
∏
p |n
p prime
(
1− 1
p2
)
=
∑
d |n
µ
(n
d
)
d2,
r(n) =

2ω(n), n ≡ 1 (mod 2) or n ≡ 4 (mod 8),
2ω(n)−1, n ≡ 2 (mod 4),
2ω(n)+1, n ≡ 0 (mod 8),
s(n) =
{
0, 4 |n or ∃p prime : (p |n and p ≡ 3 (mod 4)),
2ψ(n), otherwise,
where ψ(n) = |{p |n; p prime, p ≡ 1(mod 4)}|.
The following formula (which can also be proved by our methods) is given in [12, Thm.
11]:
Theorem 1.4. The number Pr(n) of isomorphism classes of generalized Petersen graphs
G(n, k) on 2n vertices with gcd(n, k) = 1 is given by
Pr(n) =
1
4
(ϕ(n) + r(n) + s(n)). (1.1)
In Section 2 we list our formulas for I(n), Ic(n), Ibc(n), P (n), Pb(n) which seem to
be new, and tabulate their values (as well as those of Pr(n)) for some small values of n. In
Section 3 we explain our proof techniques and give the proofs.
2 The main results
Theorem 2.1. Let n = pk11 p
k2
2 · · · p
kω(n)
ω(n) be the prime factorization of n. Then the number
of isomorphism classes of I-graphs on 2n vertices is given by
I(n) =
1
4
4∑
i=1
ω(n)∏
j=1
gi
(
p
kj
j
)
−
{
2τ(n)− 1, n even,
τ(n), n odd, (2.1)
M. Petkovšek and H. Zakrajšek: Enumeration of I-graphs: Burnside does it again 245
where
g1(pk) =
(p+ 1)pk − 2
p− 1
, (2.2)
g2(pk) =
{
4k, p = 2,
2k + 1, p > 2, (2.3)
g3(pk) =
 2, p = 2 and k = 1,4(k − 1), p = 2 and k ≥ 2,2k + 1, p > 2, (2.4)
g4(pk) =
 2, p = 2,2k + 1, p ≡ 1 (mod 4),1, p ≡ 3 (mod 4). (2.5)
Theorem 2.2. The number P (n) of isomorphism classes of generalized Petersen graphs
on 2n vertices is given by
P (n) =
1
4
(2n− ϕ(n)− 2 gcd(n, 2) + r(n) + s(n)). (2.6)
Theorem 2.3. The number of isomorphism classes of connected I-graphs on 2n vertices is
given by
Ic(n) =
1
4
(
J2(n)
ϕ(n)
+ r(n) + s(n) + t(n)
)
−
 1, n odd,2, n ≡ 0 (mod 4),3, n ≡ 2 (mod 4) (2.7)
where
t(n) =
{
2ω(n) + 2ω(n/2), n even,
2ω(n), n odd.
(2.8)
Theorem 2.4. For n even, let χ(n) = (n/2) mod 2. The number of isomorphism classes
of bipartite generalized Petersen graphs on 2n vertices is given by
Pb(n) =
{
1
4 (n− ϕ(n)− 2χ(n) + r(n) + s(n)) , n even
0, n odd. (2.9)
Theorem 2.5. For n even, let χ(n) = (n/2) mod 2. The number of isomorphism classes
of bipartite connected I-graphs on 2n vertices is given by
Ibc(n) =
{
1
4
(
J2(n)
3ϕ(n) + χ(n) 2
ω(n/2) + r(n) + s(n)
)
− χ(n), n even
0, n odd.
(2.10)
Corollary 2.6. Let p be an odd prime. Then
I(p) = Ic(p) = P (p) = Pr(p) =
⌈p
4
⌉
.
246 Ars Math. Contemp. 2 (2009) 241–262
n 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
I(n) 1 1 2 3 2 4 4 6 3 11 4 7 10 10 5 14 5 17 12
Ic(n) 1 1 2 2 2 3 3 4 3 7 4 5 7 6 5 8 5 10 9
P (n) 1 1 2 2 2 3 3 4 3 5 4 5 6 6 5 7 5 8 8
Pr(n) 1 1 2 1 2 2 2 2 3 2 4 2 3 3 5 2 5 3 4
n 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
I(n) 11 6 28 10 14 13 21 8 35 8 22 17 18 17 41 10 19
Ic(n) 8 6 14 8 10 9 13 8 19 8 12 13 13 13 19 10 14
P (n) 8 6 11 8 10 9 11 8 13 8 12 12 13 12 15 10 14
Pr(n) 3 6 4 6 4 5 4 8 3 8 5 6 5 7 4 10 5
n 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
I(n) 20 40 11 44 11 31 32 23 12 60 16 36 25 37 14 49 24
Ic(n) 15 20 11 25 11 19 19 17 12 26 14 22 19 22 14 26 19
P (n) 14 17 11 18 11 17 17 17 12 21 14 20 18 20 14 22 18
Pr(n) 7 6 11 4 11 6 7 6 12 6 11 6 9 7 14 5 11
n 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
I(n) 50 27 30 15 93 16 31 40 46 29 64 17 47 32 63 18 96
Ic(n) 26 21 22 15 40 16 23 25 24 23 37 17 28 25 37 18 38
P (n) 23 20 22 15 27 16 23 23 24 22 28 17 26 24 29 18 31
Pr(n) 8 10 8 15 6 16 8 10 9 14 6 17 9 12 7 18 8
n 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
I(n) 19 38 49 51 30 75 20 84 40 42 21 117 36 43 40 72
Ic(n) 19 28 31 31 25 43 20 38 27 31 21 52 29 32 31 38
P (n) 19 28 28 29 24 33 20 33 27 31 21 37 28 32 30 35
Pr(n) 19 10 11 10 16 7 20 10 14 11 21 8 18 11 15 12
n 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103
I(n) 23 120 35 61 42 47 38 122 25 62 57 93 26 95 26
Ic(n) 23 55 29 37 33 35 31 50 25 41 37 46 26 55 26
P (n) 23 39 28 35 32 35 30 41 25 38 35 40 26 43 26
Pr(n) 23 7 19 12 16 12 19 10 25 11 16 11 26 9 26
Table 2: The values of I(n), Ic(n), P (n), Pr(n) for 3 ≤ n ≤ 103.
M. Petkovšek and H. Zakrajšek: Enumeration of I-graphs: Burnside does it again 247
n 104 105 106 107 108 109 110 111 112 113 114 115 116
I(n) 84 85 54 27 131 28 91 50 106 29 104 45 77
Ic(n) 44 51 40 27 55 28 55 39 50 29 61 37 46
P (n) 41 42 40 27 45 28 45 38 45 29 48 36 44
Pr(n) 14 14 14 27 10 28 11 19 14 29 10 23 15
n 117 118 119 120 121 122 123 124 125 126 127 128 129
I(n) 66 59 44 208 36 62 55 81 48 153 32 94 57
Ic(n) 43 44 37 78 33 46 43 49 38 73 32 48 45
P (n) 41 44 36 55 33 46 42 47 38 54 32 48 44
Pr(n) 19 15 25 12 28 16 21 16 26 10 32 17 22
n 130 131 132 133 134 135 136 137 138 139 140 141 142
I(n) 108 33 167 48 67 96 106 35 124 35 163 62 71
Ic(n) 65 33 76 41 50 55 56 35 73 35 76 49 53
P (n) 54 33 57 40 50 50 53 35 58 35 59 48 53
Pr(n) 14 33 12 28 17 19 18 35 12 35 14 24 18
Table 3: The values of I(n), Ic(n), P (n), Pr(n) for 105 ≤ n ≤ 142.
n 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36
Ibc(n) 1 1 2 2 3 2 3 3 4 3 6 4 5 7 5 5 7
Pb(n) 1 1 2 2 3 2 3 3 4 3 6 4 5 6 5 5 7
n 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68
Ibc(n) 5 8 9 7 6 10 8 8 9 10 8 14 8 9 13 10
Pb(n) 5 8 8 7 6 10 8 8 9 10 8 13 8 9 12 10
n 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100
Ibc(n) 13 14 10 11 15 14 11 18 11 14 19 13 12 18 14 16
Pb(n) 12 14 10 11 14 14 11 17 11 14 17 13 12 18 14 16
n 102 104 106 108 110 112 114 116 118 120 122 124 126
Ibc(n) 19 16 14 19 19 18 21 16 15 28 16 17 25
Pb(n) 18 16 14 19 18 18 20 16 15 26 16 17 23
n 128 130 132 134 136 138 140 142 144 146 148 150 152
Ibc(n) 17 23 26 17 20 25 26 18 26 19 20 31 22
Pb(n) 17 22 25 17 20 24 25 18 26 19 20 28 22
Table 4: The values of Ibc(2n) and Pb(2n) for 2 ≤ n ≤ 76.
248 Ars Math. Contemp. 2 (2009) 241–262
3 The proofs
3.1 The Burnside technology
Let α be the action of a finite group G on a finite set A. Then we denote by ∼α the
associated equivalence relation on A, by |A/∼α| the number of orbits of α, and by fixα(g)
the number of elements of A fixed by g ∈ G under α. Our main enumeration tool is the
Cauchy-Frobenius-Burnside lemma:
Lemma 3.1.
|A/∼α| =
1
|G|
∑
g∈G
fixα(g).
For a proof, see, e.g., [11, Lemma 7.24.5]).
First we list some auxiliary results which will be useful in the sequel.
Proposition 3.2. Let ϑn be the multiplicative action of Z∗n on Zn. Then
|Zn/∼ϑn| =
1
ϕ(n)
∑
a∈Z∗n
gcd(n, a− 1). (3.1)
Proof. Assume that j ∈ Zn, a ∈ Z∗n, d = gcd(n, a− 1), n = n′d and a− 1 = a′d. Then
gcd(n′, a′) = 1, and so j is fixed by a iff
aj ≡ j (mod n) ⇐⇒ n | (a− 1)j ⇐⇒ n′ | a′j ⇐⇒ n′ | j.
It follows that the set of j fixed by a is {0, n′, 2n′, . . . , (d − 1)n′}, hence fixϑ(a) = d =
gcd(n, a− 1), and Lemma 3.1 gives (3.1).
Lemma 3.3. Let a, d, n ∈ N be such that d |n and gcd(a, d) = 1. Then there is an x ∈ Z
such that gcd(a+ xd, n) = 1.
Proof. Let x ∈ Zn satisfy
x 6≡ −a d−1 (mod p)
for each prime p which divides n but not d. Note that d is invertible mod p for such p, and
that such an x exists by the Chinese Remainder Theorem.
Assume that gcd(a + xd, n) 6= 1. Then there exists a prime p such that p |n and
p | (a+ xd). We distinguish two cases.
a) If p | d then p | a, contrary to the assumption that gcd(a, d) = 1.
b) If p 6 | d then
a+ xd ≡ 0 (mod p) =⇒ x ≡ −a d−1 (mod p),
contrary to the choice of x.
In either case we reach a contradiction, hence gcd(a+ xd, n) = 1.
Corollary 3.4. Let ϑn be as in Proposition 3.2. For all j, k ∈ Zn we have:
(i) j ∼ϑn gcd(n, j),
M. Petkovšek and H. Zakrajšek: Enumeration of I-graphs: Burnside does it again 249
(ii) j ∼ϑn k ⇐⇒ gcd(n, j) = gcd(n, k),
(iii) each orbit of ϑn contains exactly one positive divisor of n (with n replaced by 0),
and |Zn/∼ϑn| = τ(n).
Proof. (i) Let d = gcd(n, j), n′ = n/d, j′ = j/d. Then gcd(n′, j′) = 1, so there are
a′, k ∈ Z such that a′j′ = 1 + kn′. Since gcd(a′, n′) = 1 and n′ |n, Lemma 3.3 implies
that there is an x ∈ Z such that a := a′ + xn′ ∈ Z∗n. Then
aj = (a′ + xn′)j′d = a′j′d+ xj′n = (1 + kn′)d+ xj′n = d+ (k + xj′)n,
hence aj ≡ d (mod n). So j ∼ϑn d, proving the claim.
(ii) Let j ∼ϑn k. Then there are a ∈ Z∗n and m ∈ Z such that aj − k = mn. This
implies that any common divisor of j and n divides k, and any common divisor of k and n
divides aj and hence j. It follows that gcd(n, j) = gcd(n, k).
Conversely, let gcd(n, j) = gcd(n, k). Then by (i), j ∼ϑn k.
(iii) By (i), each orbit of ∼ϑn contains a positive divisor of n (with n replaced by 0).
By (ii), different positive divisors of n (with n replaced by 0) belong to different orbits of
∼ϑn . This proves the claim.
Lemma 3.5. Let a, b, c ∈ Z, n, k ∈ N.
(i) If a ≡ b (mod n) then gcd(a, n) = gcd(b, n).
(ii) If gcd(a, b) = 1 then gcd(ab, c) = gcd(a, c) gcd(b, c).
(iii) Any set of nk consecutive integers contains exactly k multiples of n.
The straightforward proofs are omitted.
Now we embark on our main task of enumerating isomorphism classes of I-graphs. For
a fixed n ≥ 3, we represent the I-graph I(n, j, k) with the ordered pair (j, k). We need to
construct a suitable group Gn acting on the set Zn × Zn in such a way that the orbits of
this action will be in one-to-one correspondence with the isomorphism classes of I-graphs.
In view of Theorem 1.1, the following choice is natural.
Definition 3.6. By Gn we denote the subgroup of the symmetric group S(Zn × Zn) gen-
erated by the permutations (ξa)a∈Z∗n , µ, ρ : Zn × Zn → Zn × Zn, where for all a ∈ Z
∗
n
and (j, k) ∈ Zn × Zn:
ξa(j, k) ≡ (aj, ak) (mod n),
µ(j, k) ≡ (j,−k) (mod n),
ρ(j, k) ≡ (k, j) (mod n).
Proposition 3.7.
Gn = {ξa, ξaµ, ξaρ, ξaρµ; a ∈ Z∗n} (3.2)
and |Gn| = 4ϕ(n).
Proof. It is straightforward to check that for all a, b ∈ Z∗n,
ξaξb = ξab,
ξaξa−1 = ξ1 = idZn×Zn = µ
2 = ρ2,
µξa = ξaµ,
ρξa = ξaρ,
µρ = ξ−1ρµ.
250 Ars Math. Contemp. 2 (2009) 241–262
Using these equalities we can show that for any g ∈ Gn there are a ∈ Z∗n and , δ ∈ {0, 1}
such that
g = ξaρµδ,
which proves (3.2). Now write gi = ξaiρ
iµδi for i ∈ {1, 2}. Assume that g1 = g2, and
compute
gi(1, 1) =
{
(ai, (−1)δiai), i = 0,
((−1)δiai, ai), i = 1.
If 1 6= 2, then g1(1, 1) = g2(1, 1) implies that a1 = (−1)δ2a2 and a2 = (−1)δ1a1,
hence a1 = (−1)δ1+δ2a1. Cancelling a1 yields (−1)δ1+δ2 = 1, and so δ1 = δ2. W.l.g.
assume that 1 = 1 and 2 = 0. Then g1 = g2 turns into ξa1ρ = ξa2 . Applying both sides
of this equality to (1, 1) yields (a1, a1) = (a2, a2), hence a1 = a2 and ξa1 = ξa2 . Now
ξa1ρ = ξa2 implies ρ = ξ1. On the other hand, the initial assumption that n ≥ 3 implies
that |Z∗n| ≥ 2, hence ρ 6= ξ1.
This contradiction shows that 1 = 2. Then g1(1, 1) = g2(1, 1) implies that a1 = a2
and (−1)δ1a1 = (−1)δ2a2, hence (−1)δ1 = (−1)δ2 , and so δ1 = δ2.
We have shown that g1 = g2 if and only if a1 = a2 and 1 = 2 and δ1 = δ2. Hence
|Gn| = 4|Z∗n| = 4ϕ(n) as claimed.
Remark 3.8. Let 〈ρ, µ〉 be the subgroup of Gn generated by ρ and µ. One can see that
〈ρ, µ〉 = {ξ1, ρ, µ, ρµ, ξ−1, ξ−1ρ, ξ−1µ, ξ−1ρµ} is isomorphic to the dihedral group D4 =
〈r, s | r4 = f2 = (rf)2 = 1〉, with r corresponding to ρµ or µρ, and f corresponding to
any of ρ, µ, ρµρ, or µρµ. The mapping h : Z∗n ×D4 → Gn defined by
h(a, rif j) = ξa(ρµ)iρj , for i ∈ {0, 1, 2, 3}, j ∈ {0, 1},
is a group epimorphism with kernel C2 = 〈(−1, r2)〉, hence by the first isomorphism
theorem for groups, Gn ' (Z∗n ×D4)/C2.
The elements of Gn are permutations of Zn × Zn, hence the group Gn acts naturally
on Zn × Zn. We denote this action by αn. In the next lemma we show how to count the
isomorphism classes in a set Kn of I-graphs on 2n vertices, by counting the orbits of αn
on an appropriate subset Kn ⊆ Zn × Zn.
Lemma 3.9. Let Kn ⊆ {I(n, j, k); j, k ∈ Z′n} be a set of I-graphs closed under isomor-
phism. Let Kn ⊆ Zn × Zn satisfy
Kn ∩ (Z′n × Z′n) = {(j, k); I(n, j, k) ∈ Kn},
and g(Kn) = Kn for all g ∈ Gn. Then the restriction of Gn to Kn,
G|Kn := {g|Kn ; g ∈ Gn},
is a subgroup of S(Kn), so let α(Kn) be the action of G|Kn on Kn. Write
ν0(Kn) = |{η ∈ Kn/∼α(Kn); η 6⊆ Z
′
n × Z′n}|.
Then
|Kn/'| = |Kn/∼α(Kn) | − ν0(Kn) (3.3)
where ' denotes graph isomorphism.
M. Petkovšek and H. Zakrajšek: Enumeration of I-graphs: Burnside does it again 251
Proof. Let us write K ′n = {(j, k) ∈ Z′n × Z′n; I(n, j, k) ∈ Kn}. Note that for any (j, k),
(j′, k′) ∈ Z′n × Z′n we have, by Theorem 1.1 and Proposition 3.7,
I(n, j, k) ' I(n, j′, k′)
⇐⇒ ∃a ∈ Z∗n : {j′, k′} ∈ {{aj, ak}, {aj,−ak}}
⇐⇒ ∃a ∈ Z∗n : (j′, k′) ∈ {(aj, ak), (ak, aj), (aj,−ak), (−ak, aj)}
⇐⇒ ∃a ∈ Z∗n : (j′, k′) ∈ {ξa(j, k), ξaρ(j, k), ξaµ(j, k), ξaρµ(j, k)}
⇐⇒ ∃g ∈ Gn : (j′, k′) = g(j, k) (3.4)
where all the arithmetic is done modulo n.
Let (j, k) ∈ K ′n and (j′, k′) = g(j, k) for some g ∈ Gn. Then I(n, j, k) ∈ Kn, and
I(n, j, k) ' I(n, j′, k′) by (3.4), hence I(n, j′, k′) ∈ Kn and (j′, k′) ∈ K ′n. It follows
that g(K ′n) = K
′
n for all g ∈ Gn, so G|K′n is a subgroup of S(K
′
n). Let α(K
′
n) be the
action of G|K′n on K
′
n. By Theorem 1.1, the mapping
f : [I(n, j, k)] 7→ [(j, k)]
from Kn/' to K ′n/∼α(K′n) is well defined and injective. Obviously it is also surjective,
hence
|Kn/'| = |K ′n/∼α(K′n)|. (3.5)
We claim that for any orbit η ∈ Kn/∼α(Kn), either η ⊆ Z′n × Z′n or η ⊆ (Zn × Zn) \
(Z′n × Z′n). To prove this, assume that η 6⊆ Z′n × Z′n. Then (0, k) ∈ η or (n/2, k) ∈ η for
some k ∈ Zn (the latter only if n is even). Hence for any (j′, k′) ∈ η, there is a g ∈ Gn
such that (j′, k′) ∈ {g(0, k), g(n/2, k)}. From Proposition 3.7 it follows that there are
a, b, c ∈ Z∗n such that {j′, k′} ∈ {{0, ak}, {bn/2, ck}}. If n is even then b is odd, hence
n |n(b − 1)/2 and bn/2 ≡ n/2 (mod n), implying that {j′, k′} ∈ {{0, ak}, {n/2, ck}}
for some a, c ∈ Z∗n. We conclude that η ⊆ (Zn×Zn)\ (Z′n×Z′n) which proves the claim.
It follows that every orbit of α(K ′n) is an orbit of α(Kn), and every orbit of α(Kn) is
either an orbit of α(K ′n) or is contained in (Zn × Zn) \ (Z′n × Z′n). Hence
|Kn/∼α(Kn)| = |K
′
n/∼α(K′n)|+ ν0(Kn),
which, together with (3.5), completes the proof.
In the rest of the paper we proceed as follows. For each of the (five) sets Kn of I-
graphs whose isomorphism classes we wish to enumerate, we select an appropriate set
Kn ⊆ Zn × Zn, and check that the assumptions of Lemma 3.9 are satisfied. Then we
count the orbits of α(Kn) by means of Lemma 3.1, which is tantamount to computing the
average number of fixed points of the elements g ∈ G|Kn . This is done by counting the
fixed points of g in four steps, corresponding to the four possible types of g, namely ξa,
ξaµ, ξaρ and ξaρµ (with a ∈ Z∗n). Finally we compute ν0(Kn) by counting those orbits of
α(Kn) that contain an element of the form (0, k) or (n/2, k), and use (3.3).
To simplify notation, we write Gn for G|Kn and αn for α(Kn) in the sequel. This
causes no confusion, since in each of the five cases considered it is straightforward to
verify that G|Kn ' Gn.
252 Ars Math. Contemp. 2 (2009) 241–262
3.2 I-graphs
Let Kn be the set of all I-graphs on 2n vertices, and Kn := Zn × Zn.
Proposition 3.10.
|Zn × Zn/∼αn| =
1
4ϕ(n)
4∑
i=1
∑
a∈Z∗n
fi(a, n)
where
f1(a, n) = gcd(n, a− 1)2,
f2(a, n) = gcd(n, a− 1) gcd(n, a+ 1),
f3(a, n) = gcd(n, a2 − 1),
f4(a, n) = gcd(n, a2 + 1).
Proof. We use Lemma 3.1. The fixed points of ξa are those pairs (j, k) which satisfy
aj ≡ j (mod n) and ak ≡ k (mod n). As in the proof of Proposition 3.2 we see that
there are d = gcd(n, a − 1) such j’s, and d such k’s, hence d2 such pairs. The number of
fixed points of all ξa is thus
∑
a∈Z∗n
f1(a, n).
The fixed points of ξaµ are those pairs (j, k) which satisfy aj ≡ j (mod n) and−ak ≡
k (mod n). There are gcd(n, a−1) such j’s, and gcd(n, a+1) such k’s, hence the number
of fixed points of all ξaµ is
∑
a∈Z∗n
f2(a, n).
The fixed points of ξaρ are those pairs (j, k) which satisfy ak ≡ j (mod n) and
aj ≡ k (mod n). Hence a2k ≡ k (mod n), and for any such k, we must take j ≡ ak
(mod n). There are gcd(n, a2− 1) such k’s, hence the number of fixed points of all ξaρ is∑
a∈Z∗n
f3(a, n).
The fixed points of ξaρµ are those pairs (j, k) which satisfy −ak ≡ j (mod n) and
aj ≡ k (mod n). Hence −a2k ≡ k (mod n), and for any such k, we must take j ≡ −ak
(mod n). There are gcd(n, a2 + 1) such k’s, hence the number of fixed points of all ξaρµ
is
∑
a∈Z∗n
f4(a, n).
Since |Gn| = 4ϕ(n), the assertion follows.
Now we wish to evaluate the sum appearing in Proposition 3.10 in closed form, given
the prime factorization of n. We do this by splitting this double sum into four single sums
correspondng to i = 1, 2, 3, 4, evaluating each of them in the case when n is a prime power,
and showing that they are multiplicative.
Lemma 3.11. For i = 1, 2, 3, 4, let
gi(n) =
1
ϕ(n)
∑
a∈Z∗n
fi(a, n)
where fi(a, n) are as in Proposition 3.10. If p is a prime and k ≥ 1, then gi(pk) are as
given in equations (2.2) – (2.5).
M. Petkovšek and H. Zakrajšek: Enumeration of I-graphs: Burnside does it again 253
Proof. Let x, r ∈ Z with gcd(r, p) = 1. Denote
νp(x) = max{i ∈ N; pi |x},
M
(r)
k,j (p) = {x ∈ Z
∗
pk − r; νp(x) ≥ j}, for 1 ≤ j ≤ k,
N
(r)
k,j (p) = {x ∈ Z
∗
pk − r; νp(x) = j}, for 0 ≤ j ≤ k − 1.
The elements of (Zpk \ Z∗pk) − r are not divisible by p, hence it follows for j ≥ 1 that
M
(r)
k,j (p) = {x ∈ Zpk − r; νp(x) ≥ j}. This is the set of all multiples of pj in a set
of pk consecutive integers, therefore Lemma 3.5 (iii) implies that |M (r)k,j (p)| = pk−j for
1 ≤ j ≤ k and for all r such that gcd(r, p) = 1. Consequently
|N (r)k,j (p)| = |M
(r)
k,j (p)| − |M
(r)
k,j+1(p)| = p
k−j − pk−j−1 for 1 ≤ j ≤ k − 1,
|N (r)k,0(p)| = |Z
∗
pk − r| − |M
(r)
k,1(p)| = ϕ(p
k)− pk−1 = pk − 2pk−1.
It follows that for any s ∈ N we have
∑
a∈Z∗
pk
gcd(pk, a− r)s =
k−1∑
j=0
|N (r)k,j (p)|p
sj + |M (r)k,k(p)|p
sk
= pk − 2pk−1 + pk
k−1∑
j=1
(p(s−1)j − p(s−1)j−1) + psk (3.6)
which for s = 1 turns into
∑
a∈Z∗
pk
gcd(pk, a− r) = (k + 1)ϕ(pk). (3.7)
Now we compute gi(pk) for i = 1, 2, 3, 4.
(i) By (3.6) with r = 1 and s = 2 we have
g1(pk)ϕ(pk) =
∑
a∈Z∗
pk
gcd(pk, a− 1)2 = pk−1((p+ 1)pk − 2),
and so g1(pk) = ((p+ 1)pk − 2)/(p− 1) as claimed in (2.2).
254 Ars Math. Contemp. 2 (2009) 241–262
(ii) For p = 2 and k ≥ 2 we find, using (3.7) in the next-to-last step, that
g2(2k)ϕ(2k) =
∑
a∈Z∗
2k
gcd(2k, a− 1) gcd(2k, a+ 1)
=
2k−1−1∑
j=0
gcd(2k, 2j) gcd(2k, 2j + 2)
= 4
2k−1−1∑
j=0
gcd(2k−1, j) gcd(2k−1, j + 1) (3.8)
= 4
2k−2−1∑
i=0
gcd(2k−1, 2i) gcd(2k−1, 2i+ 1)
+ 4
2k−2−1∑
i=0
gcd(2k−1, 2i+ 1) gcd(2k−1, 2i+ 2)
= 4
2k−2−1∑
i=0
gcd(2k−1, 2i) + 4
2k−2−1∑
i=0
gcd(2k−1, 2i+ 2)
= 8
2k−2−1∑
i=0
gcd(2k−1, 2i) = 8
∑
a∈Z∗
2k−1
gcd(2k−1, a− 1)
= 8k ϕ(2k−1) = 4k ϕ(2k), (3.9)
as claimed in (2.3). The case k = 1 is easily verified directly.
If p > 2 then at most one of a− 1, a+ 1 is divisible by p. Hence we find, using (3.7),
that
g2(pk)ϕ(pk) =
∑
a∈Z∗
pk
gcd(pk, a− 1) gcd(pk, a+ 1)
=
∑
a∈Z∗
pk
gcd(pk, a− 1) +
∑
a∈Z∗
pk
gcd(pk, a+ 1)−
∑
a∈Z∗
pk
1
= 2(k + 1)ϕ(pk)− ϕ(pk) = (2k + 1)ϕ(pk)
and (2.3) follows.
M. Petkovšek and H. Zakrajšek: Enumeration of I-graphs: Burnside does it again 255
(iii) For p = 2 and k ≥ 2 we obtain
g3(2k)ϕ(2k) =
∑
a∈Z∗
2k
gcd(2k, a2 − 1) =
2k−1−1∑
j=0
gcd(2k, (2j + 1)2 − 1)
= 4
2k−1−1∑
j=0
gcd(2k−2, j(j + 1))
= 4
2k−1−1∑
j=0
gcd(2k−2, j) gcd(2k−2, j + 1)
= 4
2k−2−1∑
j=0
gcd(2k−2, j) gcd(2k−2, j + 1)
+ 4
2k−2−1∑
j=0
gcd(2k−2, j + 2k−2) gcd(2k−2, j + 1 + 2k−2)
= 8
2k−2−1∑
j=0
gcd(2k−2, j) gcd(2k−2, j + 1)
= 8(k − 1)ϕ(2k−1) = 4(k − 1)ϕ(2k)
by (3.8) and (3.9). The case k = 1 is easily verified directly.
If p > 2 then at most one of a− 1, a+ 1 is divisible by p. It follows that gcd(pk, a2 −
1) = gcd(pk, a− 1) gcd(pk, a+ 1), and so g3(pk) = g2(pk) = 2k + 1, proving (2.4).
(iv) For p = 2 we have
g4(2k)ϕ(2k) =
∑
a∈Z∗
2k
gcd(2k, a2 + 1) =
2k−1−1∑
j=0
gcd(2k, (2j + 1)2 + 1)
= 2
2k−1−1∑
j=0
gcd(2k−1, 2j2 + 2j + 1) = 2 · 2k−1 = 2ϕ(2k).
Assume that p ≡ 1 (mod 4). Then −1 is a quadratic residue modulo pk, so there is an
r ∈ Z such that r2 ≡ −1 (mod pk). By Lemma 3.5 (i), gcd(pk, a2 + 1) = gcd(pk, a2 −
r2), hence
g4(pk)ϕ(pk) =
∑
a∈Z∗
pk
gcd(pk, a2 + 1) =
∑
a∈Z∗
pk
gcd(pk, a2 − r2)
=
∑
a∈Z∗
pk
gcd(pk, (a− r)(a+ r)).
If p | a − r and p | a + r then p | 2a which is false, since p is odd and a ∈ Z∗pk . Hence at
most one of a− r, a+ r is divisible by p. Now by the same argument as in (ii) we find that
g4(pk)ϕ(pk) = (2k + 1)ϕ(pk), hence g4(pk) = 2k + 1.
256 Ars Math. Contemp. 2 (2009) 241–262
Finally, let p ≡ 3 (mod 4). Then −1 is a quadratic nonresidue modulo p, hence
gcd(pk, a2 + 1) = 1 for all a. It follows that
g4(pk)ϕ(pk) =
∑
a∈Z∗
pk
gcd(pk, a2 + 1) = ϕ(pk)
and so g4(pk) = 1, proving (2.5).
It remains to show that g1(n), g2(n), g3(n), g4(n) are multiplicative.
Lemma 3.12. Let
g(n) =
∑
a∈Z∗n
r∏
k=1
gcd(n, Pk(a))
where P1(x), P2(x), . . . , Pr(x) are polynomials in x with integer coefficients. Then g(n)
is a multiplicative arithmetic function.
Proof. Let n = n1n2 where gcd(n1, n2) = 1. We need to show that g(n) = g(n1)g(n2).
For a ∈ Zn, let a1 ∈ Zn1 and a2 ∈ Zn2 be such that
a ≡ a1 (mod n1), a ≡ a2 (mod n2).
By the Chinese Remainder Theorem, the mapping
f : a 7→ (a1, a2)
is a bijection from Zn to Zn1 × Zn2 . By Lemma 3.5 (i) and (ii), gcd(n1n2, a) = 1 iff
gcd(n1, a) = gcd(n2, a) = 1 iff gcd(n1, a1) = gcd(n2, a2) = 1, therefore f restricted to
Z∗n is a bijection from Z∗n to Z∗n1 × Z
∗
n2 . Also, Pk(a) ≡ Pk(ai) (mod ni) for i = 1, 2,
hence by Lemma 3.5 (i) and (ii),
gcd(n1n2, Pk(a)) = gcd(n1, Pk(a)) gcd(n2, Pk(a))
= gcd(n1, Pk(a1)) gcd(n2, Pk(a2)).
It follows that
g(n1n2) =
∑
(a1,a2)∈Z∗n1×Z
∗
n2
r∏
k=1
gcd(n1, Pk(a1)) gcd(n2, Pk(a2))
=
∑
a1∈Zn1
r∏
k=1
gcd(n1, Pk(a1))
∑
a2∈Zn2
r∏
k=1
gcd(n2, Pk(a2))
= g(n1)g(n2),
proving multiplicativity of g(n).
Proof of Theorem 2.1:
Clearly I(n) = |Kn/'|, and the assumptions of Lemma 3.9 are satisfied. We still
need to compute ν0(Zn × Zn). From Corollary 3.4 (iii) it follows that the set Un :=
({0} × Zn)∪ (Zn × {0}) equals the union of τ(n) orbits with representatives (0, k) where
k |n (with k = n replaced by 0). So if n is odd, ν0(Zn × Zn) = τ(n). If n is even, the set
Vn := ({n/2} × Zn)∪ (Zn × {n/2}) equals the union of τ(n) orbits with representatives
(n/2, k) where k |n (with n replaced by 0). The two sets Un and Vn share the orbit con-
taining (n/2, 0), hence in this case ν0(Zn×Zn) = 2τ(n)− 1. Equation (2.1) now follows
by Lemma 3.9, using Proposition 3.10, Lemma 3.11 and Lemma 3.12.
M. Petkovšek and H. Zakrajšek: Enumeration of I-graphs: Burnside does it again 257
3.3 Generalized Petersen graphs
Let Kn be the set of all generalized Petersen graphs on 2n vertices, and
Kn := Z∗n × Zn ∪ Zn × Z∗n.
Proposition 3.13.
|Kn/∼αn| =
1
4
(2n− ϕ(n) + 2 gcd(n, 2) + r(n) + s(n)) (3.10)
Proof. We use Lemma 3.1. Assume that (j, k) ∈ Kn is fixed by some g ∈ Gn.
a) If g = ξa then (aj, ak) = (j, k). Since {j, k} ∩ Z∗n 6= ∅, it follows that a ≡ 1
(mod n). So
∑
a∈Z∗n
fixαn(ξa) = fixαn(ξ1) = |Kn| = n2 − (n − ϕ(n))2 = ϕ(n)(2n −
ϕ(n)).
b) If g = ξaµ then (aj,−ak) = (j, k). Since {j, k} ∩ Z∗n 6= ∅, it follows that a ≡
±1 (mod n). In one case, 2k ≡ 0 (mod n), so k = 0 or k = n/2 if n is even, and
j ∈ Z∗n. In the other, the roles of j and k are reversed. So fixαn(ξ1µ) = fixαn(ξ−1µ) =
gcd(n, 2)ϕ(n), and
∑
a∈Z∗n
fixαn(ξaµ) = 2 gcd(n, 2)ϕ(n).
c) If g = ξaρ then (ak, aj) = (j, k). In this case a2j ≡ j (mod n) and a2k ≡ k
(mod n), so a2 ≡ 1 (mod n), j, k ∈ Z∗n, and k ≡ aj (mod n) is determined by the
choice of j ∈ Z∗n. Thus
∑
a∈Z∗n
fixαn(ξaρ) = r(n)ϕ(n).
d) If g = ξaρµ then (−ak, aj) = (j, k). In this case a2j ≡ −j (mod n) and a2k ≡
−k (mod n), so a2 ≡ −1 (mod n), j, k ∈ Z∗n, and k ≡ aj (mod n) is determined by
the choice of j ∈ Z∗n. Thus
∑
a∈Z∗n
fixαn(ξaρµ) = s(n)ϕ(n).
Equation (3.10) now follows from Lemma 3.1.
Proof of Theorem 2.2:
Clearly P (n) = |Kn/'|. It follows from Theorem 1.1 that I(n, j, k) is isomorphic to
a generalized Petersen graph if and only if j ∈ Z∗n or k ∈ Z∗n, hence the assumptions of
Lemma 3.9 are satisfied. We still need to compute ν0(Kn), the number of orbits containing
pairs of the form (0, k) or (n/2, k) with k ∈ Z∗n. There are two such orbits if n is even,
and one if n is odd, hence ν0(Kn) = gcd(n, 2). Equation (2.6) now follows by Lemma
3.9, using Proposition 3.13.
3.4 Connected I-graphs
Let Kn be the set of all connected I-graphs on 2n vertices, and
Kn := {(j, k) ∈ Zn × Zn; gcd(n, j, k) = 1}.
Proposition 3.14.
|Kn/∼αn| =
1
4
(
J2(n)
ϕ(n)
+ r(n) + s(n) + t(n)
)
(3.11)
where t(n) = t1(n) + t2(n) is given in (2.8).
Proof. We use Lemma 3.1. Assume that (j, k) ∈ Kn is fixed by some g ∈ Gn.
a) If g = ξa then (aj, ak) = (j, k). Let d = gcd(n, a−1), n = n′d and a−1 = a′d. As
in the proof of Proposition 3.2, we see that n′ | j and n′ | k. Since n′ |n as well, it follows
258 Ars Math. Contemp. 2 (2009) 241–262
that n′ = 1 and so n | a − 1, which is only possible if a = 1. Thus ξa has no fixed points
unless a = 1. As ξ1 fixes all points in Kn, we have∑
a∈Z∗n
fixαn(ξa) = fixαn(ξ1) = |Kn| = J2(n).
b) If g = ξaµ then (aj,−ak) = (j, k). Denote nj = gcd(n, j) and nk = gcd(n, k).
Any common divisor of nj and nk is a common divisor of n, j, k, hence nj ⊥ nk and
njnk |n. Denote n0 = n/(njnk), j′ = j/nj , k′ = k/nk. Then
n = n0njnk, j′ ∈ Z∗n0nk , k
′ ∈ Z∗n0nj .
From aj ≡ j (mod n) it follows that n0nk | (a−1)j′, hence n0nk | a−1. From ak ≡ −k
(mod n) it follows that n0nj | (a + 1)k′, hence n0nj | a + 1. Therefore n0 | 2, and so
n0 ∈ {1, 2} and ϕ(n0) = 1.
We claim that for each pair (j, k) where j = j′nj , k = k′nk, n = n0njnk, n0 ∈ {1, 2},
nj ⊥ nk, j′ ∈ Z∗n0nk and k
′ ∈ Z∗n0nj , there is a unique a ∈ Z
∗
n such that aj ≡ j (mod n)
and ak ≡ −k (mod n). Indeed, let n =
∏m
i=1 p
ei
i be the prime factorization of n (i.e.,
p1, p2, . . . , pm are distinct primes and ei ≥ 1 for i = 1, 2, . . . ,m). Define a ∈ Z by
requiring that for each i ∈ {1, 2, . . . ,m},
a ≡ −1 (mod peii ) if p
ei
i |n0nj ,
a ≡ 1 (mod peii ) if p
ei
i |n0nk.
At least one of peii |n0nj and p
ei
i |n0nk holds for each i ∈ {1, 2, . . . ,m}, and both hold
only if peii = n0 = 2, hence these requirements are consistent, and by the Chinese Remain-
der Theorem, there is a unique a ∈ Zn which satisfies them. In fact, a2 ≡ 1 (mod peii )
for i = 1, 2, . . . ,m, hence a2 ≡ 1 (mod n), and so a ∈ Z∗n. Note that a is odd if n0 = 2,
therefore n0 | a− 1 and n0 | a+ 1.
If peii |n0nj then p
ei
i |n0j | (a− 1)j. Also, a ≡ −1 (mod p
ei
i ), so p
ei
i | (a+ 1)k.
If peii |n0nk then p
ei
i |n0k | (a+ 1)k. Also, a ≡ 1 (mod p
ei
i ), so p
ei
i | (a− 1)j.
In either case, peii | (a−1)j and p
ei
i | (a+1)k. As this holds for all i ∈ {1, 2, . . . ,m}, it
follows that n | (a− 1)j and n | (a+ 1)k, hence aj ≡ j (mod n) and ak ≡ −k (mod n)
as claimed.
Thus to construct (j, k) ∈ Kn which is fixed by some ξaµ, first select n0, nj , nk, j′,
k′ ∈ Zn such that n0 ∈ {1, 2}, nj ⊥ nk, n = n0njnk, j′ ∈ Z∗n0nk and k
′ ∈ Z∗n0nj , then
take j = j′nj , k = k′nk. This can be done in∑
n0∈{1,2},nj⊥nk,n=n0njnk
ϕ(n0nk)ϕ(n0nj)
ways. W.l.g. assume that nk is odd. Then ϕ(n0nk)ϕ(n0nj) = ϕ(n0)ϕ(nk)ϕ(n0nj) =
ϕ(nk)ϕ(n0nj) = ϕ(n0njnk) = ϕ(n), hence∑
a∈Z∗n
fixαn(ξaµ) = ϕ(n)(t1(n) + t2(n))
where tn0(n) = |{(nj , nk); nj ⊥ nk, n = n0njnk}|. Clearly, t1(n) = 2ω(n) and
t2(n) =
{
2ω(n/2), n even,
0, n odd.
M. Petkovšek and H. Zakrajšek: Enumeration of I-graphs: Burnside does it again 259
c) If g = ξaρ then (ak, aj) = (j, k). In this case gcd(n, j, aj) = gcd(n, j, k) = 1 by
Lemma 3.5 (i), and a2j ≡ j (mod n). It follows that j ∈ Z∗n and a2 ≡ 1 (mod n). Since
k ≡ aj (mod n) is determined by the choice of j ∈ Z∗n, we have
∑
a∈Z∗n
fixαn(ξaρ) =
r(n)ϕ(n).
d) If g = ξaρµ then (−ak, aj) = (j, k). In this case gcd(n, j, aj) = gcd(n, j, k)
= 1 by Lemma 3.5 (i), and a2j ≡ −j (mod n). It follows that j ∈ Z∗n and a2 ≡ −1
(mod n). Since k ≡ aj (mod n) is determined by the choice of j ∈ Z∗n, we have∑
a∈Z∗n
fixαn(ξaρµ) = s(n)ϕ(n).
Equation (3.11) now follows from Lemma 3.1.
Proof of Theorem 2.3:
Clearly Ic(n) = |Kn/'|. It follows from Theorem 1.2 that the assumptions of Lemma
3.9 are satisfied. We still need to compute ν0(Kn), the number of orbits containing pairs
of the form (0, k) or (n/2, k) with k ∈ Z∗n.
If (0, k) ∈ Kn then gcd(n, k) = gcd(n, 0, k) = 1, hence k ∈ Z∗n. It follows that all
such pairs belong to a single orbit of αn.
Assume that n ≡ 0(mod 4). If (n/2, k) ∈ Kn then gcd(n, n/2, k) = 1. Since in
this case gcd(n, n/2, k) = 1 iff gcd(n, k) = 1, it follows that k ∈ Z∗n. For any a ∈ Z∗n
we have a(n/2) ≡ n/2(mod n), hence we conclude again that all such pairs belong to a
single orbit of αn.
Assume that n ≡ 2 (mod 4). If (n/2, k) ∈ Kn then gcd(n, n/2, k) = 1. In this
case it is straightforward to see that gcd(n, n/2, k) = 1 iff k = 2ja for some j ≥ 0 and
a ∈ Z∗n. All the pairs (n/2, a) with a ∈ Z∗n clearly belong to a single orbit of αn. Now
we claim that 4Z∗n = 2Z∗n. Indeed, let q = n/2 and a ∈ Z∗n. Then gcd(2a + q, n) = 1
and 4a ≡ 2(2a + q) (mod n), proving that 4Z∗n ⊆ 2Z∗n. Conversely, if q ≡ 1 (mod 4)
then gcd((q + 1)/2, n) = 1 and 2a ≡ 4a(q + 1)/2 (mod n). If q ≡ 3 (mod 4) then
gcd((3q + 1)/2, n) = 1 and 2a ≡ 4a((3q + 1)/2) (mod n), proving that 2Z∗n ⊆ 4Z∗n,
and also the claim. Hence all the pairs (n/2, 2ja) with j ≥ 1 and a ∈ Z∗n also belong
to a single orbit of αn. On the other hand, all the pairs in the orbit of (n/2, 1) have one
component in Z∗n, while all the pairs in the orbit of (n/2, 2) have neither component in Z∗n,
hence these two orbits are distinct.
It follows that
ν0(Kn) =
 1, n ≡ 1 (mod 2),2, n ≡ 0 (mod 4),3, n ≡ 2 (mod 4),
which together with Lemma 3.9 and Proposition 3.14 yields (2.7).
3.5 Bipartite generalized Petersen graphs
Let Kn be the set of all bipartite generalized Petersen graphs on 2n vertices, and
Kn := Z∗n × Zon ∪ Zon × Z∗n,
where Zon is the subset of odd elements in Zn.
Proposition 3.15. Let n be even. Then
|Kn/∼αn | =
1
4
(n− ϕ(n) + 2 ((n/2) mod 2) + r(n) + s(n)) . (3.12)
260 Ars Math. Contemp. 2 (2009) 241–262
Proof. We follow the proof of Proposition 3.13. Assume that (j, k) ∈ Kn is fixed by some
g ∈ Gn, and notice that both j and k are odd.
a) If g = ξa then (aj, ak) = (j, k). From {j, k}∩Z∗n 6= ∅ it follows that a ≡ 1 (mod n).
So
∑
a∈Z∗n
fixαn(ξa) = |Kn| = (n/2)2 − (n/2− ϕ(n))2 = ϕ(n)(n− ϕ(n)).
b) If g = ξaµ then (aj,−ak) = (j, k). If j ∈ Z∗n, then a ≡ 1 (mod n) and 2k ≡
0 (mod n). As k is odd, this is only possible if n 6≡ 0 (mod 4) and k = n/2. If k ∈ Z∗n,
then a ≡ −1 (mod n), n 6≡ 0 (mod 4) and j = n/2. So fixαn(ξ1µ) = fixαn(ξ−1µ) =
ϕ(n)(n/2 (mod 2)), and
∑
a∈Z∗n
fixαn(ξaµ) = 2ϕ(n)(n/2 (mod 2)).
c), d): As in the proof of Proposition 3.13.
Equation (3.12) now follows from Lemma 3.1.
Proof of Theorem 2.4:
Clearly Pb(n) = |Kn/' |. It follows from Theorems 1.1 and 1.3 that I(n, j, k) is
isomorphic to a bipartite generalized Petersen graph if and only if j ∈ Z∗n and k is odd,
or k ∈ Z∗n and j is odd, hence the assumptions of Lemma 3.9 are satisfied. We still need
to compute ν0(Kn), the number of orbits containing pairs of the form (n/2, k) with n/2
odd and k ∈ Z∗n. There are no such orbits if n ≡ 0 (mod 4), and one such orbit if n ≡ 2
(mod 4). Hence
ν0(Kn) = (n/2) mod 2,
which together with Lemma 3.9 and Proposition 3.15 yields (2.9).
3.6 Bipartite connected I-graphs
Let Kn be the set of all bipartite connected I-graphs on 2n vertices, and
Kn := {(j, k) ∈ Zn × Zn; gcd(n, j, k) = 1, j, k odd}.
Proposition 3.16. Let n be even. Then
|Kn/∼αn | =
1
4
(
J2(n)
3ϕ(n)
+ ((n/2) mod 2) 2ω(n/2) + r(n) + s(n)
)
. (3.13)
Proof. We follow the proof of Proposition 3.14. Assume that (j, k) ∈ Kn is fixed by some
g ∈ Gn.
a) If g = ξa then (aj, ak) = (j, k). As in case a) in the proof of Proposition 3.14, we
see that a ≡ 1 (mod n), thus
∑
a∈Z∗n
fixαn(ξa) = fixαn(ξ1) = |Kn|. Let
Un := {(j, k) ∈ Zn × Zn; gcd(n, j, k) = 1, j odd, k even},
Vn := {(j, k) ∈ Zn × Zn; gcd(n, j, k) = 1, j even, k odd},
Wn := {(j, k) ∈ Zn × Zn; gcd(n, j, k) = 1}.
Define the functions fn : Kn → Un and gn : Un → Kn by
fn(j, k) := (j, k + j) (mod n),
gn(j, k) := (j, k − j) (mod n).
Clearly gcd(n, j, k) = 1 iff gcd(n, j, k + j) = 1 iff gcd(n, j, k − j) = 1. Next, for j, k
odd, k + j (mod n) is even, and if j is odd and k is even, then k − j (mod n) is odd.
M. Petkovšek and H. Zakrajšek: Enumeration of I-graphs: Burnside does it again 261
Since fn(gn(j, k)) = (j, k) = gn(fn(j, k)), we conclude that fn and gn are bijections,
and |Kn| = |Un|. Since Wn = Kn ∪ Un ∪ Vn, |Wn| = J2(n), and |Un| = |Vn| by
symmetry, it follows that |Kn| = |Un| = |Vn| = J2(n)/3.
b) If g = ξaµ then (aj,−ak) = (j, k). As in case b) in the proof of Proposition 3.14,
we see that n = n0njnk where n0 | 2, nj | j and nk | k. Since n is even while j and k
are odd, it follows that n0 = 2, hence ξaµ has no fixed points if n ≡ 0 (mod 4). So
assume that n ≡ 2 (mod 4). To construct (j, k) ∈ Kn which is fixed by some (uniquely
determined) ξaµ, first select nj , nk, j′, k′ ∈ Zn such that nj ⊥ nk, n = 2njnk, j′ ∈ Z∗2nk
and k′ ∈ Z∗2nj , then take j = j
′nj , k = k′nk. This can be done in∑
nj⊥nk,n=2njnk
ϕ(2nk)ϕ(2nj)
ways. Since nk and nj are odd, ϕ(2nk)ϕ(2nj) = ϕ(nk)ϕ(2nj) = ϕ(2nknj) = ϕ(n).
Therefore
∑
a∈Z∗n
fixαn(ξaµ) = ϕ(n) 2
ω(n/2) if n ≡ 2 (mod 4). By multiplying this
expression with (n/2) mod 2 we extend its validity to all even n.
c), d): As in the proof of Proposition 3.14.
Equation (3.13) now follows from Lemma 3.1.
Proof of Theorem 2.5:
Clearly Ibc(n) = |Kn/'|. It follows from Theorems 1.2 and 1.3 that the assumptions
of Lemma 3.9 are satisfied. We still need to compute ν0(Kn), the number of orbits con-
taining pairs of the form (n/2, k) with n/2 and k odd and gcd(n, n/2, k) = 1. In this
case gcd(n, n/2, k) = 1 if and only if gcd(n, k) = 1. Therefore there are no such orbits if
n ≡ 0 (mod 4), and one such orbit if n ≡ 2 (mod 4). Hence
ν0(Kn) = (n/2) mod 2,
which together with Lemma 3.9 and Proposition 3.16 yields (2.10).
4 Concluding remark
It is not difficult to see that the numbers Ic(n) and I(n) of isomorphism classes of con-
nected I-graphs resp. all I-graphs on 2n vertices satisfy the pair of Moebius inverse rela-
tions
I(n) =
∑
d |n
Ic(d), Ic(n) =
∑
d |n
µ(n/d)I(d)
(cf. [8, Sec. 3]).
5 Acknowledgement
The authors wish to express their thanks to the referees for their careful reading of the paper
and useful suggestions.
References
[1] M. Boben, T. Pisanski and A. Žitnik, I-graphs and the corresponding configurations, J. Combin.
Des. 13 (2005), 406–424.
262 Ars Math. Contemp. 2 (2009) 241–262
[2] I. Z. Bouwer, W. W. Chernoff, B. Monson and Z. Star, The Foster Census, Charles Babbage
Research Centre, 1988.
[3] R. Frucht, J. E. Graver and M. E. Watkins, The groups of the generalized Petersen graphs, Proc.
Camb. Phil. Soc. 70 (1971), 211–218.
[4] B. Horvat, T. Pisanski and A. Žitnik, All generalized Petersen graphs are unit-distance graphs,
submitted.
[5] B. Horvat, T. Pisanski and A. Žitnik, Isomorphism checking of I-graphs, submitted.
[6] V. A. Liskovets and A. D. Mednykh, On the number of connected and disconnected coverings
over a manifold, Ars Math. Contemp. 2 (2009), 181–189.
[7] A. Orbanić, M. Petkovšek, T. Pisanski and P. Potočnik, A note on enumeration of one-vertex
maps, Ars Math. Contemp., to appear.
[8] M. Petkovšek and T. Pisanski, Counting disconnected structures: chemical trees, fullerenes,
I-graphs, and others, Croat. Chem. Acta 78 (2005), 563–567.
[9] T. Pisanski, D. Schattschneider and B. Servatius, Applying Burnside’s lemma to a one-
dimensional Escher problem, Math. Mag. 79 (2006), 167–180.
[10] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at
http://www.research.att.com/˜njas/sequences/.
[11] R. P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge,
1999.
[12] A. Steimle and W. Staton, The isomorphism classes of the generalized Petersen graphs, Dis-
crete Math. 309 (2009), 231–237.
[13] M. E. Watkins, A theorem on Tait colorings with an application to the generalized Petersen
graphs, J. Comb. Theory 6 (1969), 152–164.