CIRCULANTS AND SEQUENCES

KAREN L. COLLINS

Abstract. A graph G is stable if its normalized chromatic difference sequence is equal to the normalized chromatic difference sequence of G × G, the Cartesian product of G with itself. Let α be the independence number of G and ω be its clique number. Suppose that G has n vertices. We show that the first ω terms of the normalized chromatic difference sequence of a stable graph G must be α/n; and further that if G has odd girth 2k + 1, then the first three terms of its normalized chromatic difference sequence are α/n, α/n, β/n, where β ≥ α/k. We derive from this sequence an upper bound on the independence ratio of G, which agrees with the lower bound of Häggkvist for k = 2 and of Albertson, Chan and Haas for k ≥ 3.

Zhou has shown that circulants and finite abelian Cayley graphs are stable. Let G be a circulant with symbol set S and n vertices. We say S = {a_{1}, a_{2}, …, a_{s}} is reversible if a_{1} + a_{s} = a_{2} + a_{s−1} = ⋯ = a_{⌊ \frac{s}{2} ⌋} + a_{⌈ \frac{s}{2} ⌋}. We show that the independence ratio μ(G) ≤ μ(S), and that if S is reversible, then lim_{n→∞} μ(G) = μ(S). We conjecture that μ(G) = μ(S) for a reversible circulant with sufficiently many vertices.

1. Introduction

Let G be a graph. The chromatic difference sequence of G, cds(G), is the sequence of positive integers of length equal to the chromatic number of G, with the ith term equal to the maximum number of vertices that can be additionally colored by using i instead of i − 1 colors, see Albertson and Berman, [1, 2]. The first appearance of this idea is Greene’s and Kleitman’s proof that comparability graphs have monotonically decreasing sequences, see [10, 11]; proofs from other perspectives and related works appear in [8, 9, 21, 23, 24]. In another direction, Stanley has developed a symmetric function generalization of the chromatic polynomial which contains the chromatic difference sequence, see [26, 27].

1991 Mathematics Subject Classification. 05C. Key words and phrases. Cayley graph, chromatic difference sequence, circulant,

graph homomorphism, independence ratio, No-homomorphism lemma, partitionable graph.

Let G have n vertices. The normalized chromatic difference sequence of G, ncds(G), is cds(G) with each term divided by n. This idea allows the chromatic sequences of graphs with different number of vertices to be fairly compared. For instance, the No-Homomorphism Lemma in [4] proves that if G ↦ H homomorphically and H is vertex transitive, then ncds(G) dominates ncds(H). Hell and Nesetril therefore think about the graph homomorphism of G to H as coloring G with H [14], see also [15, 16, 17, 19, 20]. Another generalization of the ncds is Zhou’s work in [30].

The first term of ncds(G) is called the independence ratio, μ(G). See also [5, 13, 18, 31] for other connections with graph homomorphism. Häggkvist uses the No-Homomorphism lemma to prove that a graph G with odd girth at least 5 and minimum degree at least (3/8)n maps homomorphically to the 5-cycle, hence μ(G) ≥ 2/5, [12]. Albertson, Chan and Haas generalize this theorem to get that if G is a graph with odd girth 2k + 1 and minimum degree at least (k/(2k + 1))n, then μ(G) ≥ k/(2k + 1), [3]. We show that if ncds(G) = ncds(G × G), then equality holds for each of these theorems. We also make a generalization to graphs with larger clique size.

A circulant G with n vertices is a vertex transitive graph with rotational symmetry such that two vertices are adjacent if their difference appears in a fixed set S. Define the size of S, |S|, to be the sum of the first and last elements of S, and μ(S) to be the independence ratio of any consecutive set of |S| vertices in G. We show that μ(S) ≥ μ(G). Let a set T be reversible if T = |T | − T. Then we show lim_{n→∞} μ(G) ≥ μ(T) whenever S ⊆ T. We also conjecture that the independence number of G with edges given by reversible T equals ⌊n · μ(T)⌋ when n is sufficiently large. In light of Zhou’s recent work [28, 29], it seems likely that these results may generalize to Cayley graphs of finite abelian groups. See also Larose, Laviolette, and Tardif [22].

Section 2 makes some useful definitions. In Section 3 we prove an upper bound that we use throughout the paper, and describe some examples. Section 4 proves the independence ratio results that coincide with those Häggkvist, and Albertson, Chan and Haas. Section 5 proves the further results on the independence ratio of circulants. We make some conjectures in Section 6.

2. Definitions

All graphs will be simple and undirected. A circulant is a graph G with n vertices labeled 0, 1, 2, …, n − 1 and edges determined by set S ⊆ \{1, 2, …, ⌊\frac{n}{2}⌋\} by i is adjacent to j if |i − j| ∈ S or n − |i − j| ∈ S. Circulant graphs are necessarily vertex transitive.

Let G and H be two graphs. Define the Cartesian product G × H to be the graph with vertex set V (G) × V (H) and edge set given by (g_{1}, h_{1}) is adjacent to (g_{2}, h_{2}) if g_{1} = g_{2} and h_{1} is adjacent to h_{2} in H or g_{1} is adjacent to g_{2} in G and h_{1} = h_{2}. Let G^{k} be the Cartesian product of G with itself k times.

Define the chromatic number of graph G, called χ(G), to be the smallest integer n such that the vertices in G can be colored with n colors so that if two vertices are adjacent, then they receive different colors. Let χ(G) = m. Define the chromatic sequence of G to be Δ_{1}, Δ_{2}, …, Δ_{m} where Δ_{i} is equal to the number of vertices in the largest i-colorable vertex induced subgraph of G.

We define the chromatic difference sequence of graph G, cds(G), to be α_{1}, α_{2}, …, α_{m} where α_{1} = Δ_{1} and α_{i} = Δ_{i} − Δ_{i−1} for 2 ≤ i ≤ m. Note that α_{1} is the independence number of G. We will abbreviate α_{1}(G) as α(G). Define the independence ratio of G to be μ(G) = α(G)/n where n is the number of vertices of G.

Let the number of vertices of G be n. Define the normalized chromatic difference sequence of G, ncds(G), to be α_{1}/n, α_{2}/n, …, α_{m}/n. Then G is said to be stable if ncds(G) = ncds(G^{2}). Define the ultimate chromatic difference sequence to be NCDS(G) = lim_{k→∞} ncds(G^{k}) [13, 30].

Note that the chromatic number of G^{k} is greater than or equal to the chromatic number of G, since G^{k} contains G as an induced subgraph. Conversely, χ(G) ≥ χ(G^{k}) by an easy argument. We let f : V (G) → {1, 2, …, χ(G)} be a coloring of G and

f(v_{1}, v_{2}, …, v_{k}) = ∑_{i=1}^{n} f(v_{i}) (modulo n)

If two vertices in G^{k} are adjacent, then they differ in only one position of their k-tuples, and hence must receive different colors modulo n.

3. An upper bound

A graph G is said to be stable if the normalized chromatic difference sequence of G is equal to the normalized chromatic difference sequence of G × G, the Cartesian product of G with itself. Zhou has shown that circulants and Cayley graphs of finite abelian groups are stable, see [28, 29]. Siran has demonstrated the existence of Cayley graphs which are not stable [25]. See also Conjecture 1.

The generalized Petersen graph P (7, 3) in Figure 1(c) is a graph which is stable but neither a circulant nor the Cayley graph of a finite abelian group. We obtain an upper bound on α(G × H) by using a clique cover of H and cds(G). This proves that a graph G cannot be stable unless the first ω(G) terms of the ncds(G) are equal.

Let A = a_{1} ≥ a_{2} ≥ ⋯ ≥ a_{s} be a partition of n. Define its conjugate partition, A^{∗}, by a_{i}^{∗} equals the number of elements of A which are at least i, for 1 ≤ i ≤ a_{1}.

Theorem 3.1. Let H be a graph, and let C = c_{1}, c_{2}, …, c_{s} be the sizes of a disjoint clique cover of H, where c_{1} ≥ c_{2} ≥ ⋯ ≥ c_{s}. Let C^{∗} be the conjugate partition of C. For any graph G,

α_{1}(G × H) ≤ ∑_{i=1}^{χ(G)} c_{i}^{∗}(H)α_{i}(G)

Proof. Let I be a maximum independent set in G × H and let I_{h} be the subset of I whose first entries are equal to h for each vertex h of H. Then I_{h} is isomorphic to an independent set in G. Clearly if h_{1} is adjacent to h_{2} in H, I_{h_{1}} ∩ I_{h_{2}} = ∅. Hence if h_{1}, h_{2}, …, h_{t} form a clique in H, then I_{h_{1}}, I_{h_{2}}, …, I_{h_{t}} are t pairwise disjoint independent sets of G, hence |I_{h_{1}} ∪ I_{h_{2}} ∪ … ∪ I_{h_{t}}| ≤ Δ_{t} = α_{1}(G) + α_{2}(G) + ⋯ + α_{t}(G), where α_{j} = 0 if j > χ(G).

Thus |I| ≤ ∑_{i=1}^{s} ∑_{j=1}^{c_{i}(H)} α_{j}(G). Each α_{j}(G) appears in the sum the same number of times as the number of cliques which have size at least j. This number is c_{j}^{∗}(H).

Corollary 3.2. Let H be a graph with |H| vertices that contains at least one edge. Let G be a graph such that α_{1}(G) > α_{i}(G) for some 2 ≤ i ≤ ω(H). Then α(G × H) < |H|α(G).

Proof. Let C_{1}, C_{2}, …, C_{t} be any disjoint clique covering of H that contains a clique of size ω(H). Since H contains an edge, c∗_{2} > 0. Note that ∑_{i=1}^{s} c_{i} = |H| = ∑_{j=1}^{c_{1}} c_{j}^{∗}. Therefore ∑_{i=1}^{l} c_{i}^{∗}(H)α_{i}(G) < |H|α_{1}(G).

Corollary 3.3. Let G be a stable graph. Then

α_{1}(G) = α_{2}(G) = ⋯ = α_{ω(G)}(G)

[figure: (a); (b); (c)]

Figure 1 The Petersen graph in (a) is not stable hence not a circulant. The tree T in (b) is not stable, but T^{2} is stable. The generalized Petersen graph P (7, 3) in (c) is stable but not a circulant, nor a finite abelian Cayley graph.

The Petersen graph (Figure 1(a)) is not a circulant, since cds(P) = 4, 3, 3. The NCDS(P^{k}) = 1/3, 1/3, 1/3, see [4]. The tree T in Figure 1(b) has cds(T) = 4, 2 and ncds(T^{2}) = 1/2, 1/2. It is easy to check that P (7, 3) in Figure 1(c) is not a circulant or the Cayley graph of a finite abelian group, and that cds(G) = 5, 5, 4. Label the outside vertices counterclockwise from the top as 1, 2, 3, 4, 5, 6, 7 and label the vertex on the inside 7-cycle which is adjacent to i as i′. Let T_{1} = {1, 3, 5}, T_{2} = {2, 4}, U_{1} = {2, 4} and U_{2} = {5, 6, 7}. All arithmetic is modulo 7. Then a maximum independent set in G^{2} with 70 vertices is {(i, j)|j ∈ (T_{1} +i−1)}∪{(i, j′)|j ∈ (T_{2} +i−1)}∪{(i′, j)|j ∈ (U_{1}+i−1)}∪{(i′, j′)|j ∈ (U_{2}+i−1)}. A second maximum independent set is given by {(i, j)|j ∈ (T_{1} + i)} ∪ {(i, j′)|j ∈ (T_{2} + i)} ∪ {(i′, j)|j ∈ (U_{1} + i)} ∪ {(i′, j′)|j ∈ (U_{2} + i)}. The graph G^{2} is 3-colorable since G is, hence ncds(G^{2}) = 5/14, 5/14, 2/7 = ncds(G) and G is stable.

The following is a direct proof that circulants satisfy Corollary 3.3.

Theorem 3.4. Let G be a circulant. Then α_{1}(G) = α_{2}(G) = ⋯ = α_{ω(G)}(G).

Proof. (Direct) Let the vertices of G be numbered from 0 to n − 1. Let I be a maximum independent set of G, and let W be a maximum clique of G. All addition is modulo n. Then {I + w|w ∈ W } is a collection of ω disjoint maximum independent sets of G. Similarly, {W + i|i ∈ I} is a collection of α disjoint maximum cliques.

4. Independence ratio of stable graphs

The cds of a stable graph G has its first ω terms equal to α. We prove that if G contains a partitionable graph H with independence number β and with the same clique size as G, then the next term in cds(G) is at least α/β. Since odd cycles are partitionable, we apply this result to graphs with large odd girth. This gives an upper bound on the independence ratio which is the same number as the lower bounds by Häggkvist and Albertson et al. when the minimum degree is bounded from below.

Define a graph G to be partitionable (or an (α, ω)-graph) if (i) n = αω + 1, (ii) every vertex v is in exactly α independent sets of size α and ω cliques of size ω, (iii) the n independent sets of size α, say S_{1}, S_{2}, …, S_{n} and the n cliques of size ω, say C_{1}, C_{2}, …, C_{n} can be ordered so that S_{i} ∩ C_{i} = ∅ and S_{i} ∩ C_{j} ≠ ∅ whenever i ≠ j. Odd cycles and their complements are partitionable. Partitionable graphs are therefore related to the Strong Perfect Graph Conjecture. See [6].

Theorem 4.1. Let G be a graph, and H be a partitionable graph such that ω(G) = ω(H) = ω. Then α(G × H) ≤ α(H) ∑_{i=1}^{ω+1} α_{i}(G).

Proof. Let α(H) = β, α(G) = α. Then consider an independent set I in G × H, where each vertex of H is replaced by a copy of G, and whenever two vertices in H are adjacent, then there is a matching between corresponding copies of G which joins isomorphic vertices of G. For every vertex v of H, let I(v) be the intersection of I and the copy of G at v.

Thus if v_{1} is adjacent to v_{2} in H, then I(v_{1}) ∩ I(v_{2}) = ∅, where I(v_{1}), I(v_{2}) are considered as subsets of the vertices of G. If v_{1}, v_{2}, …, v_{t} is a clique in H, then I(v_{1}), I(v_{2}), …, I(v_{t}) is a collection of disjoint independent sets of G, that is, a partial coloring of G. Thus | ∪_{j=1}^{t} I(v_{j})| ≤ ∑_{j=1}^{t} α_{j}(G).

Label the vertices of H with 0 to β·ω so that in (H −0) the β disjoint ω-cliques are C_{1}, C_{2}, …, C_{β} where m ∈ C_{i} exactly when (i − 1)ω + 1 ≤ m ≤ i·ω. Let J(0) = I(0) and J(k) = ⋃(I(0)∩I(j_{1})∩I(j_{2})∩… I(j_{k})) where (i − 1)ω + 1 ≤ j_{i} ≤ i · ω for 1 ≤ i ≤ k. Each term in the union is non-empty if and only if the vertices 0, j_{1}, j_{2}, …, j_{k} form an independent set in H. Notice that J(k) ⊆ J(k − 1).

Then we partition the vertices of I into β disjoint (ω + 1)-colorable subgraphs of G. Let G_{i} = (J(i − 1) − J(i)) ∪ (⋃_{r=1}^{ω} I((i − 1) · ω + r). Notice that J(i) = ⋃_{r=1}^{ω} (I((i − 1)ω + r) ∩ J(i − 1)); hence when J(i) is subtracted from J(i − 1), we have removed J(i − 1) ∩ ⋃_{r=1}^{ω} I((i − 1)ω + r) from J(i − 1). Also, (i − 1)ω + 1, (i − 1)ω + 2, …, i · ω forms a clique in H, hence G_{i} is the union of ω + 1 disjoint independent sets of G. Thus |G_{i}| ≤ ∑_{s=1}^{ω+1} α_{s}(G).

Now the question remains whether we have included every vertex of I(0) in our partition. At each step i we include J(i − 1) − J(i), so that what we have remaining to include is J(i). Thus after partitioning β times, one for each of the ω cliques of H, we have remaining J(β) = ⋃(I(0) ∩ I(j_{1}) ∩ I(j_{2}) ∩ … I(j_{β})). But J(β) must be empty, since 0, j_{1}, j_{2}, …, j_{β} is a set of size β + 1 and hence cannot be independent in H. Hence |I| ≤ ∑_{i=1}^{β} |G_{i}| ≤ β(∑_{i=1}^{ω+1} α_{i}(G)).

For example, if H is the 5-cycle, then α(G×H) ≤ 2(α_{1}(G)+α_{2}(G)+ α_{3}(G).

The argument above can be applied separately to disjoint subgraphs of H to bound α(G × H) further.

Theorem 4.2. Let G be a stable graph, and let H be an induced subgraph of G which is partitionable, and ω(G) = ω(H). Let α(H) = β, α(G) = α. Then

α_{ω(G)+1}(G) ≥ α/β
β/(βω + 1) ≥ μ(G)

Proof. Suppose that I is a maximum independent set in G^{2}. Since G is stable, α(G^{2}) = |G|α(G), hence if we consider G^{2} as replacing each vertex of G with a copy of G, we must have that a maximum independent set in G^{2} intersects each of the |G| copies of G in α(G) vertices. Let I(H) be I restricted to H × G. Thus |I(H)| = |H|α(G). Now by Corollary 3.3 α = α_{1}(G) = α_{2}(G) = ⋯ = α_{ω}(G). By the previous lemma, then |I(H)| = (βω + 1)α ≤ β(ωα + α_{ω+1}), so α/β ≤ α_{ω+1}(G).

Let n be the number of vertices of G. Then n ≥ ∑_{i=1}^{ω+1} α_{i}(G) ≥ α(ω + 1/β), so we get μ ≤ β/(βω + 1).

Define σ(G) to be the size of the smallest chordless odd cycle of G. Let σ(G) = 0 if G has no chordless odd cycle, i.e. G is bipartite.

Corollary 4.3. Let G be a stable graph with n vertices, and σ(G) ≥ 2l + 1. Then α(G)/l ≤ α_{3}(G) and μ(G) ≤ l/(2l + 1).

Proof. The first half of the proof follows from Theorem 4.2 and the fact that a 2l + 1 cycle is partitionable and has independence number l.

This lower bound on μ(G) can be combined with the following results. Let δ(G) be equal to the minimum vertex degree of G.

Theorem 4.4 (Häggkvist [12]). Let G be a graph with n vertices, σ(G) ≥ 5 and δ > (3n)/8. Then μ(G) ≥ 2/5.

Theorem 4.5 (Albertson, Chan and Haas [3]). Let l > 2. Let G be a graph with n vertices, σ(G) ≥ 2l + 1 and δ > n/(l + 1). Then μ(G) ≥ l/(2l + 1).

Corollary 4.6. Let G be a stable graph, σ(G) ≥ 5 and δ(G) > 3n/8. Then μ(G) = 2/5.

Corollary 4.7. Let l > 2 and let G be a stable graph, σ(G) ≥ 2l + 1 and δ(G) > n/(l + 1). Then μ(G) = l/(2l + 1).

In particular, any circulant G with n vertices and δ(G) > n/(l + 1) satisfies α(G)/n = l/(2l + 1). Since gcd(l, 2l + 1) = 1, 2l + 1 must divide n. Thus if 2l + 1 does not divide n, G must have σ(G) ≤ 2l − 1. If G is a circulant with δ(G) > 3n/8 and 5 does not divide n, then G has a triangle.

Theorem 4.1 still holds if the graph H is replaced by the kth power of a cycle where the clique size does not divide the number of vertices. These circulants appear in Seymour’s conjecture, see [7]. Let W (m, l) be the circulant with m vertices and S = {1, 2, 3, …, l} such that m = j(l + 1) + r and r ≠ 0. Then W (m, l) has ω = l + 1, α = j and χ = l + 2. When r = 1, W (m, l) is partitionable.

Theorem 4.8. Let G be a graph. Let m = j(l + 1) + r, where r ≠ 0. Then α(W (m, l)) = j and α(G × W (m, l)) ≤ j ∑_{i=1}^{l+2} α_{i}(G) + ∑_{i=1}^{r−1} α_{i}(G).

Proof. The proof is an easy generalization of the proof of Theorem 4.1.

Corollary 4.9. Let G be a stable graph that contains W (m, l) such that l + 1 does not divide m. Then α_{l+2}(G) ≥ α(G)/α(W (m, l)) and μ(G) ≤ α(W (m, l))/((l + 1)j + 1).

5. Independence ratio of circulants

We prove that the independence ratio of circulant G with edge set given by S is less than or equal to the independence ratio of a graph U(S) that depends only on S. This upper bound is therefore independent of the number of vertices in G. We then show that the limit of the independence ratio of a reversible circulant as the number of vertices goes to infinity equals the independence ratio of U(S). We show two methods to embed a circulant which is not reversible into a circulant which is reversible, thus getting lower bounds for the limit of the independence ratio of any circulant.

Let l ≥ 2. Let S = {a_{1}, a_{2}, …, a_{l}} be the edge set of circulant G. Let |S| = a_{1} + a_{l}. Let U(S) be the graph with vertices labeled 0, 1, 2, …, (|S| − 1) such that i is adjacent to j if |i − j| ∈ S. Then U(S) is not a circulant because we are not including as edges the vertices i and j where |i − j| ∈ |S| − S. We abbreviate α(U(S)) and ω(U(S)) as α(S) and ω(S) respectively. Let μ(S) = α(S)/|S|. Then we get the following upper bound on the independence ratio. See also Conjecture 2.

Theorem 5.1. Let G be a circulant with n vertices and edge set given by S. Then μ(S) ≥ μ(G).

Proof. Let n = q|S|+r with 0 ≤ r ≤ |S|−1. Let I be a fixed maximum independent set of G and let H_{j,k} = {j, j + 1, j + 2, …, j + k − 1} with arithmetic modulo n. Let i be the minimum of |H(j, r) ∩ I| over 0 ≤ j ≤ n − 1. If i/r ≤ μ(S), we show μ(G) ≤ μ(S). Observe that any consecutive |S| vertices of the circulant intersect with I in at most α(S) vertices. Therefore we can break up the circulant into q groups of |S| and one group of r vertices, choosing the r vertices so that we achieve i as the minimum intersection with I. Then α(G) ≤ qα(S) + i ≤ qα(S) + rα(S)/|S| = \frac{α(S)}{|S|}(q|S| + r) = n\frac{α(S)}{|S|}. Hence μ(G) ≤ μ(S).

Suppose that i/r > α(S)/|S|. Define |S| = r_{0} and r = r_{1}. Let r_{l+2} = r_{l+1}(⌊\frac{r_{l}}{r_{l+1}} ⌋ + 1) − r_{l} for nonnegative integer l. Let i_{l+2} be the minimum of |H(j, r_{l+2} ∩I|. Then we prove that μ(S) < i/r < i_{2}/r_{2} < ⋯ < i_{L}/r_{L} where r_{L} is the greatest common divisor of n and |S|. This gives the following contradiction: i_{L}|S|/r_{L} > α(S) ≥ |H(j, |S|)∩I| ≥ i_{L}(|S|/r_{L}).

Now gcd(n, |S|) = gcd(|S|, r) by the Euclidean algorithm. Since r_{l+2} is an integer linear combination of r_{l+1} and r_{l}, we have gcd(r_{l}, r_{l+1}) = gcd(r_{l+1}, r_{l+2}) for all nonnegative integers l. Let r_{l} = q · r_{l+1} + m with 0 ≤ m ≤ r_{l+1} − 1. Then r_{l+2} = r_{l+1}(q + 1) − r_{l} = r_{l+1} − m. Clearly r_{l+2} = r_{l+1} − m < r_{l+1} unless m = 0, in which case r_{l+1} divides r_{l} and r_{l+1} = gcd(n, |S|). Therefore the sequence r_{0}, r_{1}, r_{2}, … is a strictly decreasing sequence of positive integers with the same greatest common divisor, which must end in r_{L} = gcd(n, |S|).

Assume by induction that i_{l}/r_{l} < i_{l+1}/r_{l+1}. Let r_{l} = q · r_{l+1} + m. Fix j. Let k_{1} = |H(j + q · r_{l+1}, m) ∩ I| and k_{2} = |H(j + r_{l}, r_{l+2}) ∩ I|. Then i_{l} ≥ |H(j, r_{l}) ∩ I| ≥ q · i_{l+1} + k_{1}. Also, k_{1} + k_{2} ≥ i_{l+1}. Hence i_{l} − q · i_{l+1} ≥ i_{l+1} + k_{2}. Since i_{l}/r_{l} < i_{l+1}/r_{l+1} we get i_{l+1}r_{l} − i_{l+1}q · r_{l+1} > i_{l+1}r_{l+1} − k_{2}r_{l+1}. Simplifying, k_{2}r_{l+1} > i_{l+1}(r_{l+1} − m). But r_{l+2} = r_{l+1} − m. Therefore, k_{2}/r_{l+2} > i_{l+1}/r_{l+1}. This inequality must hold for any value of j, hence it holds when k_{2} is the minimum value, so i_{l+2}/r_{l+2} > i_{l+1}/r_{l+1}.

Theorem 5.2. Let G be a circulant with n vertices and edge set given by S. Then 1/ω(S) ≥ μ(G).

Proof. For any circulant G, n ≥ α(G)ω(G) by Theorem 3.4, hence 1/ω(G) ≥ μ(G). Let S = {a_{1}, a_{2}, …, a_{l}}. Then n ≥ 2a_{l} by our definition of S. Thus U(S) has a_{1} + a_{l} vertices and G has at least that many. We argue that ω(G) ≥ ω(S), hence 1/ω(S) ≥ 1/ω(G) ≥ μ(G). Let the vertices of G be labeled 0, 1, 2, …, n − 1. Then a copy of U(S) is embedded in the subgraph of G induced by 0, 1, 2, …, (a_{1} + a_{l} − 1). Thus ω(G) ≥ ω(S).

For any integer k, let k−S = {k−a_{1}, k−a_{2}, …, k−a_{l}}. Define a set S to be reversible if |S|−S = S. Note that this means S is reversible if and only if a_{i} + a_{l+1−i} = |S| for all 1 ≤ i ≤ l. We show that a circulant G with n vertices and reversible set S maps homomorphically to the circulant H with n − |S| vertices and the same set S.

Lemma 5.3. Let H be a reversible circulant with n vertices and with edge set given by S. Let n > |S|. Let G be the circulant with n + |S| vertices and edge set given by S. Then G maps homomorphically to H.

Proof. Let the vertices of H be {0, 1, 2, …, n − 1} and the vertices of G be {0, 1, 2, …, n + |S| − 1}. We define a homomorphism f : G → H by f(i) = i if 0 ≤ i ≤ n − 1 and f(i + n) = i if 0 ≤ i ≤ |S| − 1. Then we show that if v and u in G are adjacent, then f(v) and f(u) are adjacent in H.

Case 1 Suppose that 0 ≤ v, u ≤ n − 1. Then if v, u are adjacent in G, |v − u| is in S or n + |S| − S. Every member of n + |S| − S is at least n, hence |v − u| is in S and since f(v) = v, f(u) = u, we have f(v), f(u) are adjacent in H.

Case 2 Suppose that 0 ≤ v, u ≤ |S| − 1. Then if v + n, u + n are adjacent in G, |(v + n) − (u + n)| is in S or n + |S| − S. But |v − u| ≤ |S| − 1, so is in S and these are adjacent in H.

Case 3 Suppose 0 ≤ v ≤ n − 1 and n ≤ u + n ≤ n + |S| − 1, and v, u + n are adjacent in G. Then |u + n − v| is in S or n + |S| − S. If u + n − v = a_{j} for some j, then v − u = n − a_{j}, so v − u is in n − S. If u + n − v = n + |S| − a_{j} for some j, then u − v = |S| − a_{j}, and since S is reversible, u − v = a_{l+1−j}, and is in S.

For any two graphs G and H for which G maps homomorphically to H, an i-colorable subgraph of H pulls back to an i-colorable subgraph of G. The No-Homomorphism lemma [4] is a special case of this fact. In the lemma below we show that in a reversible circulant, we can find a large independent set which is based on a fixed small circulant with the same set of edges, by folding the large circulant onto the small one.

Lemma 5.4. Let H be a reversible circulant with n vertices and with edge set given by S. Let a_{l} be the largest element of S and let n > |S| + a_{l}. Let G(k) be the circulant with n + (k − 1) · |S| vertices and edge set given by S. Then α(G(k)) ≥ α(H) + (k − 1)α(S). Further, lim_{k→∞} μ(G(k)) ≥ μ(S).

Proof. Note that G(1) = H. By Lemma 5.3 G(k + 1) maps homomorphically to G(k) for each positive integer k, and hence we have a homomorphism from G(k + 1) to H for every k. This map is f_{k} : G(k) → H by f_{k}(i) = i for 0 ≤ i ≤ n − 1 and f_{k}(i + jn) = i for 0 ≤ i ≤ |S| − 1 and 1 ≤ j ≤ k − 2. Any independent set in H can be pulled back to form an independent set in G(k), since the pre-image of a vertex in H is an independent set of vertices in G(k). In particular we choose an independent set with as many vertices as possible chosen from 0, 1, 2, …, |S| − 1 in H. Since n > |S| + a_{l}, n − a_{l} > |S| and there are no edges whose difference is in n − S in the range of vertices 0, 1, 2, …, |S| − 1. Then α(G(k)) ≥ α(H) + (k − 1) · α(S) ≥ kα(S). Hence the lim_{k→∞} μ(G(k)) ≥ lim_{k→∞} kα(S)/(n + (k − 1) · |S|) ≥ μ(S). Thus we get

lim_{k→∞} μ(G(k)) ≥ lim_{k→∞} \frac{kα(S)}{(n + (k − 1) · |S|)} = μ(S) lim_{k→∞} \frac{k}{(n/|S| + k − 1)} = μ(S)

Let S = {a_{1}, a_{2}, …, a_{l}} be a set which is not reversible. Then S can be embedded in a larger set which is reversible. This will add edges to the circulant which has S as its edge set, which may make the largest independent set smaller. Let a_{l−1} + a_{l} = D and a_{1} + a_{l} = E. Let Ŝ = S ∪ (D − S) and S̃ = S ∪ (E − S). Then it is easy to check that Ŝ, S̃ are reversible and contain S. If S is reversible, define Ŝ, S̃ = S. Note that α(Ŝ) ≥ α(S), since we have added only larger terms to S.

Corollary 5.5. Let G be a circulant with n vertices and edge set given by S = {a_{1}, a_{2}, …, a_{l}}. Define L(S) = lim_{n→∞} μ(G). Then μ(S), 1/ω(G) ≥ L(S) ≥ μ(Ŝ), μ(S̃). If G is reversible, then L(S) = μ(S).

We apply these bounds to two special cases: a circulant with every element of S odd, and a circulant with S containing just 2 elements.

Corollary 5.6. Let G be a circulant with n vertices and edge set given by S which contains only odd numbers. Then L(S) = 1/2.

Proof. Since G is a circulant, and ω(G) ≥ 2, α_{1}(G) = α_{2}(G), hence n ≥ 2α_{1}(G) and μ(G) ≤ 1/2. If n is even, then G is bipartite, hence ncds(G) = 1/2, 1/2. If n is odd, then G is not bipartite, but either S or Ŝ contains only odd numbers. Therefore α(Ŝ) = |Ŝ|/2 by taking all vertices whose labels are even and less that |Ŝ|. Thus μ(Ŝ) = 1/2 and Corollary 5.5 finishes the proof.

Corollary 5.7. Let G be a circulant with n vertices and edge set given by S = {a, b}. Let n > 2(a + b). Let q, r satisfy b = qa + r with 0 ≤ r ≤ a − 1. Then

L(S) = \{ \begin{matrix}\frac{b+r}{2(a+b)} & q even \\ \frac{b+(a−r)}{2(a+b)} & q odd \end{matrix}

Proof. We apply Corollary 5.5. Suppose that q is even. Then {i + 2ja|0 ≤ i ≤ a−1, 0 ≤ j ≤ (q−2)/2}∪{qa, qa+1, qa+2, …, qa+r−1} is an independent set in U(S) and we can take α(S) ≥ aq/2+r = (b+r)/2. If q is odd, then {i + 2ja|0 ≤ i ≤ a − 1, 0 ≤ j ≤ (q − 1)/2} is an independent set in U(S) and α(S) ≥ a(q + 1)/2 = (b + (a − r))/2. Dividing by |S| = a + b gives the result.

For example, L({1, 2k}) = k/(2k + 1).

S Best lower bound Best upper bound
1, 2, 4 1/ω(S) = 1/3  μ(Ŝ) = 1/3
1, 2, 5 1/ω(S) = 1/3  μ(S̃) = 1/3
1, 2, 6 μ(S) = 2/7 μ(S̃) = 2/7
1, 2, 7 1/ω(S) = 1/3  μ(Ŝ) = 1/3
1, 3, 4 1/ω(S) = 1/3  μ(Ŝ) = 2/7
1, 3, 6 1/ω(S) = 1/3  μ(Ŝ) = 1/3
1, 4, 5 1/ω(S) = 1/3  μ(Ŝ) = 1/3
1, 4, 6  μ(S) = 3/7  μ(Ŝ) = 2/5
1, 4, 7  μ(S) = 3/8  μ(Ŝ) = 3/8
1, 5, 6 1/ω(S) = 1/3  μ(S̃) = 2/7
1, 6, 7 1/ω(S) = 1/3  μ(Ŝ) = 4/13

Figure 2 provides best upper and lower bounds for L(S) for some small values of S. See Conjecture 3.

6. Conjectures

A circulant (or Cayley graph) G not only is stable, but all of its Cartesian powers G^{k} are stable. The graph in Figure 1(c) is not a circulant, but it is stable, which leads to the following conjecture.

Conjecture 1. If G is stable, then G^{k} is stable for all positive integers k.

Let G, H be reversible with edge set given by S as described in Lemma 5.4, and n is the number of vertices of H. Then μ(S) ≥ μ(G) ≥ (α(H) + (k − 1)α(S))/(n + (k − 1)|S|). Hence n · μ(S) + α(S)(k − 1) ≥ α(G) ≥ α(H) + α(S)(k − 1). We conjecture that for n as large as in Lemma 5.4, α(G) is always as large as possible. It is necessary that n be large; if H is the circulant with S = {1, 5} and n = 11, then μ(S) = 1/2, but μ(H) = 3/11, and 11/2 is much greater than 3.

Conjecture 2. Let G be a reversible circulant with n vertices and edge set given by S = {a_{1}, a_{2}, …, a_{l}}. If n > |S|+a_{l} then α(G) = ⌊n·μ(S)⌋.

By Corollary 5.5, we have L(S) ≥ μ(Ŝ), μ(S̃), Figure 2 shows that L({1, 2, 4}) = μ(Ŝ), and L({1, 2, 5}) = μ(S̃).

Conjecture 3. L(S) = max{μ(Ŝ), μ(S̃)}.

References

[1] M. O. Albertson and D. M. Berman, The chromatic difference sequence of a graph, JCT(B), 29 (1980), pp. 1-12.

[2] M. O. Albertson and D. M. Berman, Critical graphs for chromatic difference sequences, Disc. Math, 31 (1980), pp. 225-233.

[3] M. O. Albertson, L. Chan and R. Haas, Independence and graph homomorphisms, to appear in JGT.

[4] M. O. Albertson and K. L. Collins, Homomorphisms of 3-chromatic graphs, Disc. Math., 54 (1985), pp. 127-132.

[5] J. A. Bondy and P. Hell A note on the star chromatic number, JGT, 14 (1990), pp. 479-482.

[6] V. Chvátal, R. L. Graham, A. F. Perold and S. H. Whitesides, Combinatorial designs related to the strong perfect graph conjecture, Disc. Math., 26 (1979), pp. 83-92.

[7] R. J. Faudree, R. J. Gould, M. S. Jacobson and R. H. Schelp, Seymour’s Conjecture, in Advances in Graph Theory, V. R. Kulli, ed., Vishwa International Pub., 1991, pp. 163-171.

[8] S. V. Fomin, Finite partially ordered sets and Young tableaux, Soviet Math. Dokl., 19 (1978), pp. 1510-1514, translation.

[9] S. V. Fomin, A duality theorem for partially ordered sets: algorithms, in Mathematical methods for constructing and analyzing algorithms, Nauka Leningrad, 237 (1990), pp. 190-199.

[10] C. Greene and D. G. Kleitman, The structure of Sperner k-families, JCT(A), 20 (1976), pp. 41-68.

[11] C. Greene, Some partitions associated with a partially ordered set, JCT(A), 20 (1976), pp. 69-79.

[12] R. Häggkvist, Odd cycles of specified lengths in non-bipartite graphs, Ann. of Disc. Math., 13 (1982), pp. 89-100.

[13] G. Hahn, P. Hell, and S. Poljak, On the ultimate independence ratio of a graph, Europ. J. Comb. 16 (1995).

[14] P. Hell and J. Nesetril, On the complexity of H-coloring, JCT(B), 48 (1990), pp. 92-110.

[15] P. Hell, J. Nesetril, and X. Zhu, Complexity of tree homomorphisms, to appear in Discrete Applied Math.

[16] P. Hell, J. Nesetril, and X. Zhu, Duality and Polynomial Testing of Tree Homomorphisms, Transactions of the A.M.S. 348 (1996) 1281 - 1297.

[17] P. Hell, J. Nesetril, and X. Zhu, Duality of graph homomorphisms, Combinatorics, Paul Erdos is Eighty Bolyai Society Mathematical Studies, vol.2, (1996), 271 - 282.

[18] P. Hell, X. Yu, and H. Zhou, Independence of Graph Powers, Discrete Math. 127 (1994) 213-220.

[19] P. Hell and X. Zhu, The existence of homomorphisms to oriented cycles, SIAM J. on Discrete Math. 8 (1995) 208 - 222.

[20] P. Hell and X. Zhu, Homomorphisms to oriented paths, Discrete Mathematics 132 (1994) 107 - 114.

[21] A. Hoffman and D. Schwartz, On partitions of a partially ordered set, JCT(B), 23 (1977), pp. 3-13.

[22] B. Larose, F. Laviolette, and C. Tardif, Normal Cayley graphs and homomorphisms of cartesian powers of graphs, preprint.

[23] M. Saks, A short proof of the existence of k-saturated partitions of a partially ordered set, Adv. in Math., 33 (1979), pp. 207-211.

[24] M. Saks, Some sequences associated with combinatorial structures, Disc. Math., 59 (1986), pp. 135-166.

[25] J. Siran, Cayley graphs for which the ultimate independence ratio is smaller than the independence number, preprint.

[26] R. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Advances in Math., 111 (1995), 166-194.

[27] R. Stanley, Graph Colorings and Related Symmetric Functions: Ideas and Applications, preprint.

[28] H. Zhou, The chromatic difference sequence of the Cartesian product of graphs, Disc. Math., 90 (1991), pp. 297-311.

[29] H. Zhou, The chromatic difference sequence of the Cartesian product of graphs, Part II, Disc. Appl. Math., 41 (1993), pp. 263-267.

[30] H. Zhou, On the Ultimate Normalized Chromatic Difference Sequences of a Graphs, Disc. Math. 148 (1966) 287-297.

[31] X. Zhu, On the bounds for the ultimate independence ratio of a graph, preprint.

Department of Mathematics, Wesleyan University, Middletown CT 06459-0128

  E-mail address: kcollins@wesleyan.edu