Automorphic chromatic index of generalized
Petersen graphs
G. Mazzuoccolo, B. Ruini
∗Abstract
The automorphic A-chromatic index of a graph Γ is the minimum integer
m for which Γ has a proper edge-coloring with m colors which is preserved
by a given subgroup A of the full automorphism group of Γ. We compute the automorphic A-chromatic index of each generalized Petersen graph when A is the full automorphism group.
Keywords: graph, edge-coloring, automorphism. MSC(2000): 05C15, 05C25.
1
Introduction
The generalized Petersen graph GP (n, k), with n and k being integers and 2 ≤ 2k < n, is the simple cubic graph with vertex-set V (GP (n, k)) = {u0, u1, . . . ,
un−1, v0, v1, . . . , vn−1} and edge-set E(GP (n, k)) = {[ui, ui+1], [ui, vi], [vi, vi+k] :
i ∈ Z}. All subscripts are taken modulo n. The edges of GP (n, k) of types [ui, ui+1], [ui, vi], and [vi, vi+k] are called outer edges, spokes, and inner edges
and they are denoted by Oi,Si and Ii, respectively; they form three n-sets that
we denote by O, S and I, respectively. The n-circuit generated by O is called the outer rim. If d denotes the greatest common divisor of n and k, then I gen-erates a subgraph which is the union of d pairwise-disjoint (n
d)-circuits, called
inner rims. The graph GP (5, 2) is the well known Petersen graph. The graph GP (n, k) with n and k relatively prime was introduced by Coxeter in [5], while the generalized Petersen graph GP (n, k) was first considered in [6]. The gen-eralized Petersen graphs have been studied by several authors: Castagna and Prins [3] completed the proof begun by Watkins in [8] that each generalized Pe-tersen graph is 3-edge-colorable, except for the original PePe-tersen graph; Alspach [1] has determined all the Hamiltonian generalized Petersen graphs; the com-plete classification of their full automorphism groups has been worked out in [6]. There exist chromatic parameters of a graph Γ that depend on the full automor-phism group of Γ: the distinguishing number defined in [2], the distinguishing chromatic number defined in [4] and the automorphic chromatic index recently
∗Dipartimento di Matematica, Universit`a di Modena e Reggio Emilia, via Campi 213/B,
defined in [7]. In [9], Weigand and Jacobson have studied and completely deter-mined the distinguishing number and the distinguishing chromatic number of each generalized Petersen graph. The aim of this paper is to do the same for the automorphic chromatic index of GP (n, k). We are interested in proper edge-colorings of the generalized Petersen graphs GP (n, k) which are preserved by the full automorphism group A(n, k). In what follows, a coloring always means a proper edge-coloring and a coloring preserved by an automorphism group A is said to be an A-automorphic coloring. The automorphic A-chromatic index of a graph Γ, denoted by χ0
A, is the minimum integer m for which Γ has an
A-automorphic coloring with m colors (see [7]). We completely determine the automorphic A(n, k)-chromatic index, χ0
A(n,k), of GP (n, k). Our main theorem
is the following: Theorem. χ0A(n,k)=
3 if n is even, k is odd and k26≡ −1 mod n
5 if n is even, k is odd and k2≡ −1 mod n
min{dn,k, en,k+ 2} otherwise,
where dn,k (en,k) is the smallest odd (even) integer dividing n and not dividing
k, if such an integer exists at all, and dn,k (en,k) = +∞ otherwise.
The previous theorem is obtained as a consequence of Theorem 2 in Section 4 and of Proposition 5 in Section 5.
2
Preliminaries
Since our parameter depends on the full automorphism group of the graph considered, we need to recall the classification of the full automorphism group, A(n, k), of GP (n, k) ([6]). Define the permutations ρ, δ, α on V (GP (n, k)) as follows:
ρ(ui) = ui+1, ρ(vi) = vi+1,
δ(ui) = u−i, δ(vi) = v−i,
α(ui) = vki, α(vi) = uki.
with all subscripts taken modulo n. Let H =< ρ, δ >, then H ≤ A(n, k) (see [8]), in particular H fixes S set-wise. The following theorem holds (see [6]): Theorem 1. If (n, k) /∈ {(4, 1), (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), (24, 5)} then
A(n, k) = (
H if k26≡ ±1 mod n
< H, α > if k2≡ ±1 mod n.
The full automorphism groups of the cases not considered in the previous proposition are described in details in the last section.
In this section we outline some properties of an H-automorphic coloring E of GP (n, k) with color-set O ∪ I ∪ S. Note that there always exists a coloring pre-served by H: the one in which each edge has a different color. We indicate with
O = {o0, o1, . . . , ol−1}, S = {s0, s1, . . . , st−1}, I = {i0, i1, . . . , im−1} the set of
colors used to color the outer edges, the spokes and the inner edges, respectively. Note that the three sets are not necessarily distinct. The cardinalities of O, S, and I are l, t and m.
Lemma 1. There exists an H-automorphic edge-coloring E of GP (n, k) if and only if
(1) m | n and m - k; (2) l | n and l > 1.
Proof. Let E be an H-automorphic coloring of GP (n, k). The action of < ρ > is transitive on the edge sets O and I, so that (as the coloring is H-automorphic) the colors are used cyclically on both these sets. Thus, we may assume E(Oj) = oj, E(Ij) = ij (where the index j is in each case taken modulo
the size of the set being indexed). Thus, l,m each divide | < ρ > | = n. More-over the adjacent edges I0, Ik and Oi, Oi+1 have different colors, then m does
not divide k and l > 1.
Vice versa consider the color-sets I and O with m, l such that m | n, m - k and l | n, l > 1. We set E(Oj) = oj, E(Ij) = ij, index j taken modulo m and l,
respectively. Furthermore, we color all spokes with a unique color s0 ∈ O ∪ I./
One can easily check that this coloring is preserved by H. ¤
In what follows we highlight some basic properties of the action of δ on the coloring E that will be useful in the next sections.
Lemma 2. Let E be an H-automorphic edge-coloring of GP (n, k). If l is even, then no color of O is fixed by the automorphism δ. If l is odd, then just one color of O is fixed by the automorphism δ.
Proof. The action of δ on O is given by δ(oj) = ol−j−1. We have δ(oj) = oj
if and only if j ≡l l − j − 1, that is 2j + 1 ≡l 0. If l is even then no colors
of O are fixed by the automorphism δ. If l is odd, since j ≤ l − 1 and then 2j + 1 ≤ 2l − 1, the unique color fixed by δ is ol−1
2 . ¤
Lemma 3. Let E be an H-automorphic edge-coloring of GP (n, k). If m is odd, then just one color of I is fixed by the automorphism δ.
If m and k are both even, then exactly two colors of I are fixed by the automor-phism δ.
Proof. The action of δ on I is given by δ(ij) = im−k−j. We have δ(ij) = ij
if and only if j ≡mm − k − j, that is 2j ≡m−k.
The color ij is fixed by δ if and only if one of the following holds
j ≡m m − k
2 (1)
j ≡m−k
If m is odd then exactly one of (1) and (2) has a solution, according to the fact that k is odd or even respectively, in both cases we have a unique color fixed by δ.
If m is even and k is even then both (1) and (2) have a solution, then we have exactly two colors fixed by δ. ¤
In Section 3 we will use the previous lemmas to determine an H-automorphic coloring of GP (n, k) with the minimum number of colors. In particular it will be useful to establish in which cases one can use the same set of colors for inner and outer edges: nevertheless in some of these cases it will be more convenient to select O and I distinct in order to minimize the total number of colors.
3
χ
0H
of GP (n, k)
In this section we determine χ0H of GP (n, k). In the rest of the paper we make
use of dn,k and en,k defined in the Main Theorem.
Proposition 1. If n is odd, then χ0
H = dn,k.
Proof. Let E be an H-automorphic coloring of GP (n, k). By Lemma 1 it follows that m is odd, m ≥ dn,kand then χ0H≥ dn,k. Now we furnish a dn,k
-col-oring preserved by H to prove the assertion. By Lemmas 2 and 3 we know that δ fixes exactly one color both in O and I, then we consider m = l = s = dn,k
and I ≡ O ≡ S = {o0, . . . , ol−1}. We set E(Oj) = oj,E(Ij) = ij with
ij = on+k+l−1
2 +j if k is odd and ij = ok+l−12 +j if k is even. Finally, we color
the spokes Sj with the color sj = ol−1
2 +j. It is easy to check that both ρ and δ
preserve the coloring and then the assertion follows. ¤
In Figure 1, we show an H-automorphic 5-coloring of GP (15, 3). Proposition 2. If n is even and k is odd, then
χ0 H= 3.
Proof. We furnish an H-automorphic 3-coloring of GP (n, k). Color Oj and
Ij either with the color o0 or with the color o1, according to the parity of j.
Observe that this is a proper coloring by the fact that n is even and k is odd. Finally, color all spokes with the color s0∈ {o/ 0, o1}.
It is straightforward to check that this coloring is preserved by H. ¤ Proposition 3. If n and k are even, then
χ0H = min{dn,k, en,k+ 2}.
Proof. If en,k < +∞ there is an H-automorphic (en,k + 2)-coloring, say
where sj = im1−k2+j (the color of the spoke Sj), and Oj colored with o0 or o1
according to the parity of j. If dn,k < +∞, there is an H-automorphic dn,k
-coloring, say E2, with colors O2∪ I2∪ S2, m2= dn,k = l2 = s2, O2= I2= S2
where ij = ol2−1+k
2 +j (the color of the inner edge Ij) and with sj = ol2−12 +j (the
color of the spoke Sj).
Now let E be an H-automorphic coloring of GP (n, k). If m is even (hence en,k< +∞), by Lemma 2 and 3 the two sets O and I are disjoint, then m ≥ en,k,
l ≥ 2; therefore χ0
H ≥ en,k+ 2. If m is odd (hence dn,k < +∞), by Lemma 1
m ≥ dn,k; hence χ0H≥ dn,k. Therefore, the statement follows. ¤
Note that there exist values of n and k, which satisfy the hypothesis of the previous proposition, such that both dn,k and en,k are finite (for instance if
n = 12 and k = 2 then en,k = 4 and dn,k= 3).
Figure 1: An H-automorphic 5-coloring of GP (15, 3)
4
General case
In this section we compute χ0
A(n,k) with (n, k) /∈ {(4, 1), (5, 2), (8, 3), (10, 2),
(10, 3), (12, 5), (24, 5)}. Recall that H ≤ A(n, k) for each n and k.
Theorem 2. If (n, k) /∈ {(4, 1), (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), (24, 5)} then χ0 A(n,k)=
3 if n is even k, is odd and k26≡ −1 mod n
5 if n is even k, is odd and k2≡ −1 mod n
min{dn,k, en,k+ 2} otherwise.
Proof. If n is even, k is odd and k2 6≡ ±1 mod n, we get A(n, k) = H (see
Proposition 1); hence from Proposition 2 it follows χ0
A(n,k)= χ0H= 3.
Let n be even, k odd and k2 ≡ 1 mod n. From Proposition 1 we have
Proposition 2. It is preserved by H. Since α fixes the set of spokes, α(Oj) = Ikj,
α(Ij) = Okj and j and kj have same parity, then α preserves the coloring E. It
follows that χ0
A(n,k)= 3 in this case.
If n is even, k odd and k2≡ −1 mod n, from Proposition 1 the automorphic
group A(n, k) is < H, α >. Suppose there exists an H-automorphic 3-coloring E of GP (n, k). Two colors o0, o1 are used to color the outer rim and a color
s0 ∈ {o/ 0, o1} is used to color the spokes. Since α(O0) = I0 and α(I0) = O−1,
then the color of the edge I0 must be different from o0, o1, s0. Therefore there
not exist a 3-coloring of GP (n, k) preserved by < H, α >. Moreover, an edge-coloring preserved by < H, α > must have at least two colors o0, o1 for the
outer rim and at least two other different colors i0, i1 for the inner rim. Hence,
a 4-coloring E of GP (n, k) preserved by < H, α > does not exist: the spokes required at least a fifth different color.
Now we describe a 5-coloring of GP (n, k) preserved by A(n, k) with set-color {o0, o1, i0, i1, s0}. Color Oj either with the color o0or o1according to the parity
of j. Color also Ijeither with the color i0or i1according to the parity of j. Color
all the spokes with the same color s0. This coloring is preserved by A(n, k). In
particular α acts on the set of colors as the permutation (o0, i0, o1, i1). Therefore,
in this case χ0
A(n,k)= 5.
Let n odd and k26≡ ±1 mod n or n even and k even. From Propositions 1
and 3 and Theorem 1 in Section 1 the statement follows (Note that if n is odd then en,k= +∞).
If n is odd and k2≡ ±1 mod n, Proposition 1 states that χ0
H= dn,k. The full
automorphism group is < H, α >. The minimal dn,k-coloring described in the
proof of Proposition 1 is preserved not only by H but also by α. In particular α acts on the set of colors as following:
α(oj) = ( ok+l−1 2 +kj if k is even on+k+l−1 2 +kj if k is odd ,
and the color ol−1
2 is fixed by α. Therefore, in this case χ 0
A(n,k) = dn,k. Since
en,k= +∞ the statement follows. ¤
5
Exceptional cases
In this section we compute χ0
A(n,k) with (n, k) ∈ {(4, 1), (5, 2), (8, 3), (10, 2),
(10, 3), (12, 5), (24, 5)}.
Define the permutation λ on V (GP (10, 2)) to have the following cycle struc-ture λ = (u0, v2, v8)(u1, v4, u8)(u2, v6, u9)(u3, u6, v9)(u4, u7, v1)(u5, v7, v3).
More-over, for (n, k) ∈ {(4, 1), (8, 3), (12, 5), (24, 5)} let σ be the permutation de-fined on V (GP (n, k)) as follows: σ(u4i) = u4i, σ(v4i) = u4i+1, σ(u4i+1) =
u4i−1, σ(u4i−1) = v4i, σ(u4i+2) = v4i−1, σ(v4i−1) = v4i+5, σ(v4i+1) = u4i−2,
σ(v4i+2) = v4i−6; finally, define the permutations µ and µ0on V (GP (10, 3)) and
(u8, v9)(v2, v8) (v3, v7) and µ0 = (u2, v1)(u3, v4)(v2, v3), respectively. Then, the
following result holds (see [6]):
Proposition 4. A(10, 2) =< ρ, λ >, A(10, 3) =< ρ, µ >, A(5, 2) =< ρ, µ0 >
and A(n, k) =< ρ, δ, σ > for (n, k) ∈ {(4, 1), (8, 3), (12, 5), (24, 5)}.
Note that H ≤ A(n, k) holds also for all exceptional cases. The following proposition complete the proof of the Main Theorem.
Proposition 5. χ0A(n,k)= ( 3 if (n, k) ∈ {(4, 1), (8, 3), (12, 5), (24, 5)} 5 if (n, k) ∈ {(5, 2), (10, 2), (10, 3)}. Proof. If (n, k) ∈ {(4, 1), (8, 3), (12, 5), (24, 5)} then χ0 A(n,k)≥ χ0(GP (n, k)) =
3. In Figure 2 an A(n, k)-automorphic 3-coloring of GP (n, k) is shown.
Figure 2: Automorphic 3-colorings of GP (4, 1), GP (8, 3), GP (12, 5) and GP (24, 5).
If (n, k) ∈ {(5, 2), (10, 2)}, then H ≤ A(n, k) and χ0
A(5,2)≥ χ0H = d5,2 = 5
(see Proposition 1) and χ0
A(10,2) ≥ χ0H = min{d10,2, e10,2+ 2} = 5 (see
Propo-sition 3). In Figure 3 an A(n, k)-automorphic 5-coloring of GP (n, k) is shown. If (n, k) = (10, 3), then χ0
A(10,3) ≥ 3, but the unique H-automorphic
3-coloring of GP (10, 3) (see Proposition 2) is not preserved by the automorphism µ of A(10, 3). Moreover, an H-automorphic 4-coloring of GP (10, 3) does not
Figure 3: Automorphic 5-colorings of GP (5, 2), GP (10, 2) and GP (10, 3) exist. An A(10, 3)-automorphic coloring of GP (10, 3) uses m colors to colors the inner rim with m | 10 and m - 3 (see Lemma 1). Since d10,3 = 5, then
χ0
A(10,3)≥ 5. In Figure 3 an A(10, 3)-automorphic 5-coloring is shown. ¤
References
[1] B. Alspach, The classification of Hamiltonian generalized Petersen graphs, J. Combin. Theory Ser. B, 34 (1983), 293-312.
[2] M.O. Albertson, K.L. Collins, Symmetry Breaking in Graphs, Electron. J. of Combin., 3 (1996), #R18.
[3] F. Castagna, G. Prins, Every generalized Petersen graph has a Tait color-ing, Pacific. J. Math., 40 (1972), 53-58.
[4] K.L.Collins, A.N.Trenk, The distinguishing chromatic number, Electron. J. of Combin., 13 (2006), #R16.
[5] H.S.M. Coxeter, Self-dual configurations and regular graphs, Bull. Amer. Math. Soc., 56 (1950), 413–455.
[6] R. Frucht, J.E. Graver, M.E. Watkins, The groups of the generalized Pe-tersen graphs, Proc. Cambridge Philos. Soc., 70 (1971), 211–218.
[7] C. Fiori, G. Mazzuoccolo, B. Ruini, On the automorphic chromatic index of a graph, submitted.
[8] M.E. Watkins, A Theorem on Tait colorings with an application to the generalized Petersen graphs, J. Combin. Theory, 6 (1969), 152–164. [9] J.Weigand and M.S.Jacobson, Distinguishing and Distinguishing
Chro-matic Numbers of Generalized Petersen Graphs, AKCE J.Graphs Combin., 5 (2008), 199-211.
