K_{p}-Removable Sequences of Graphs

John P. McSorley London Guildhall University, Dept. of CISM, 100 Minories, London, EC3N 1JY. mcsorley60@hotmail.com

Thomas D. Porter, Department of Mathematics, Southern Illinois University, Carbondale. IL 62901-4408. tporter@math.siu.edu

Abstract

Let {G_{pn} | n ≥ 1} = {G_{p1}, G_{p2}, G_{p3}, …} be a countable sequence of simple graphs, where G_{pn} has pn vertices. This sequence is called K_{p}- removable if G_{p1} = K_{p}, and G_{pn} − K_{p} = G_{p(n−1)} for every n ≥ 2 and for every K_{p} in G_{pn}. We give a general construction of such sequences. We specialize to sequences in which each G_{pn} is regular; these are called regular (K_{p}, λ)-removable sequences, λ is a fixed number, 0 ≤ λ ≤ p, referring to the fact that G_{pn} is (λ(n − 1) + p − 1)-regular. We classify regular (K_{p}, 0)-, (K_{p}, p − 1)-, and (K_{p}, p)-removable sequences as the sequences {nK_{p} | n ≥ 1}, {K_{p×n} | n ≥ 1}, and {K_{pn} | n ≥ 1} respectively. Regular sequences are also constructed using ‘levelled’ Cayley graphs, based on a finite group. Some examples are given.

Keywords: removable, Cayley, isomorphism, reconstruction, clique

1 Notation, K_{p}-removable sequences of graphs, main results

For p ≥ 1 and n ≥ 1 let K_{p} be the complete graph on p vertices, let nK_{p} be n disjoint copies of K_{p}, and let K_{p×n} = K\underbrace{n,...,n}_{p}, be the complete p -partite graph

on pn vertices. All graphs G are simple. In the graph G let G[{v_{1}, …, v_{m}}] = G[v_{1}, …, v_{m}] denote the induced subgraph on vertices {v_{1}, …, v_{m}}. Suppose that for some p vertices {v_{1}, …, v_{p}} in G we have G[v_{1}, …, v_{p}] = K_{p}, i.e., G[v_{1}, …, v_{p}] is an induced K_{p}, then G − K_{p} denotes the subgraph obtained from G by deleting vertices v_{i} and their incident edges, for every i = 1, …, p. If two graphs G and G′ are isomorphic we write G ≅ G′. We often say that two graphs are ‘equal’ (=) instead of ‘isomorphic’, and say ‘K_{p}’ instead of ‘induced K_{p}’.

For the countable sequence of graphs {G_{pn} | n ≥ 1} = {G_{p1}, G_{p2}, G_{p3}, …} we use the notation {G_{pn}}, each graph G_{pn} has pn vertices for a fixed p ≥ 1.

We call a sequence {G_{pn}} K_{p}-removable if it satisfies the following two properties:

A1 G_{p1} ≅ K_{p},

A2 G_{pn} − K_{p} ≅ G_{p(n−1)} for every n ≥ 2 and every (induced) K_{p} in G_{pn}.

In this paper we investigate K_{p}-removable sequences. In Section 2 we give a general construction for such sequences. In Section 3 we specialize to sequences in which each graph is regular; we call these regular (K_{p}, λ)- removable sequences, λ is a fixed number, 0 ≤ λ ≤ p, referring to the fact that G_{pn} is (λ(n−1)+p−1)-regular. We classify regular (K_{p}, 0)-, (K_{p}, p − 1)-, and (K_{p}, p)-removable sequences as the sequences {nK_{p}}, {K_{p×n}}, and {K_{pn}} respectively, thus associating three well-known graphs on pn vertices. In Section 4 we construct regular (K_{p}, λ)-removable sequences starting from a finite group; the graphs in this sequence are similar in construction to Cayley graphs, we also count the number of K_{p}’s in these graphs.

2 Construction of a K_{p}-removable sequence for every p ≥ 3, examples

From A1 and A2 above we see that if {G_{pn}} is K_{p}-removable then G_{p1} = K_{p} and G_{p2} is the union of this K_{p} and a ‘new’ K_{p}, together with some edges between them. The graph G_{p3} is then formed from G_{p2} by adding another K_{p} and some suitable set of edges between this new K_{p} and the previous two K_{p}’s, and so on. Thus G_{pn} contains at least n disjoint K_{p}’s. We use this idea of constructing G_{pn} by adding K_{p} to K_{p}, up to n K_{p}’s, in the following:

Here p ≥ 3 and [p] = {1, …, p}. Let Λ = (Λ_{1}, …, Λ_{p}) be an ordered p-tuple of subsets of [p], i.e., each Λ_{i} ⊆ [p].

Consider a K_{p} with vertices labelled {(1, 1), …, (p, 1)} = {(i, 1) | i ∈ [p]}; call these vertices vertices at level 1, and call this graph H_{p1}^{Λ}. Now consider another K_{p} with vertices labelled {(i, 2) | i ∈ [p]}, vertices at level 2. For any vertex (i, 2) join it to vertices {(i′, 1) | i′ ∈ Λ_{i}} at level 1; call this graph H_{p2}^{Λ}. Now consider a third K_{p} with vertices labelled {(i, 3) | i ∈ [p]}, at level 3. Join any vertex (i, 3) to vertices {(i′, 2) | i′ ∈ Λ_{i}} at level 2 and to vertices {(i′, 1) | i′ ∈ Λ_{i}} at level 1; this is H_{p3}^{Λ}.

For any n ≥ 1, consider the graph which has been constructed level by level, up to n levels, according to the above definition; call this graph H_{pn}^{Λ}. In H_{pn}^{Λ} the vertices are of the form (i, j) for every i ∈ [p] and every 1 ≤ j ≤ n, (where j is their level); and the edges are of two types:

(i) fixed-level edges, say at level j

((i_{1}, j), (i_{2}, j)) is an edge for all i_{1}, i_{2} ∈ [p] where i_{1} ≠ i_{2}; and

(ii) cross-level edges, for j > j′

((i, j), (i′, j′)) is an edge if and only if i′ ∈ Λ_{i}.

For each i ∈ [p] let λ_{i} = |Λ_{i}| be the number of elements in Λ_{i}, and let μ_{i} be the number of sets in Λ which contain i. Call Λ uniform if:

i ∉ Λ_{i} and λ_{i} = μ_{i} for each i ∈ [p].  (1)

From now on let our Λ be uniform. In Theorem 2.3 we show that if Λ is uniform then {H_{pn}^{Λ}} is K_{p}-removable.

For any fixed i ∈ [p], let I_{i} = {(i, 1), …, (i, n)} = {(i, j) | 1 ≤ j ≤ n} be the set of vertices of H_{pn}^{Λ} in ‘column i’. Then, because i ∉ Λ_{i}, this is an independent set of vertices.

Now let W be a K_{p} in H_{pn}^{Λ}, then each of the p independent sets I_{1}, …, I_{p} contains exactly one vertex from W; let I_{i} contain vertex (i, w_{i}) ∈ W, a vertex at level w_{i}, for some 1 ≤ w_{i} ≤ n. Thus W = H_{pn}^{Λ}[(1, w_{1}), …, (p, w_{p})]=K_{p}.

Lemma 2.1 Let Λ be uniform. For any K_{p} = W in H_{pn}^{Λ} the number of edges in H_{pn}^{Λ} − W equals the number of edges in H_{p(n−1)}^{Λ}.

Proof. Consider any vertex (i, j) in H_{pn}^{Λ}, here 1 ≤ j ≤ n. It is adjacent to λ_{i} vertices at each of the j − 1 levels lower than level j, i.e., to λ_{i}(j − 1) such vertices, and to p − 1 vertices at level j, and to μ_{i}(n − j) vertices at levels higher than level j. Thus, because λ_{i} = μ_{i}, its degree is

deg((i, j)) = λ_{i}(n − 1) + p − 1.  (2)

So if (i, j) is in W = K_{p}, then its degree ‘outside’ W is λ_{i}(n − 1), which is independent of its level, j.

Now W contains exactly one vertex from each independent set I_{i}, so, when removing W, we remove ∑_{i=1}^{p}(λ_{i}(n − 1)) edges ‘outside’ W, (and \binom{p}{2} ‘inside’ W). But this equals the number of edges removed if we remove the K_{p} at level n (because deg((i, n)) is also given by (2)), leaving the graph H_{p(n−1)}^{Λ}. Hence, the number of edges in H_{pn}^{Λ} − W equals the number of edges in H_{p(n−1)}^{Λ}.

Lemma 2.2 Let Λ be uniform. For any p ≥ 3, n ≥ 2, and any K_{p} = W in H_{pn}^{Λ}, we have

H_{pn}^{Λ} − W = H_{p(n−1)}^{Λ}.

Proof. Let the vertices of W be {(i, w_{i}) | 1 ≤ i ≤ p}. We construct a bijection ϕ between the vertices of H_{pn}^{Λ} − W and the vertices of H_{p(n−1)}^{Λ}, and then show that ϕ is an isomorphism. Under ϕ, for a fixed i ∈ [p], the vertices in the i-th independent set of H_{pn}^{Λ} − W, namely in the set I_{i}\{(i, w_{i})}, are mapped to the vertices in the i-th independent set of H_{p(n−1)}^{Λ}, namely to the set {(i, 1), …, (i, n − 1)}, as follows:

(i, n)  → (i, n − 1)
·  ·
·  ·
·  ·
(i, w_{i} + 1) → (i, w_{i})
(i, w_{i} − 1) → (i, w_{i} − 1)
·  ·
·  ·
·  ·
(i, 1)  → (i, 1)

i.e.,

ϕ(i, j) = \{ \begin{matrix}(i, j − 1), & for w_{i} < j ≤ n; \\ (i, j), & for 1 ≤ j < w_{i}. \end{matrix}

Clearly ϕ is a bijection.

There are two types of edges in H_{pn}^{Λ}: fixed-level edges and cross-level edges. First we deal with fixed-level edges.

A typical fixed-level edge in H_{pn}^{Λ} is ((i_{1}, j), (i_{2}, j)) for some i_{1}, i_{2} ∈ [p] where i_{1} ≠ i_{2} and for some j with 1 ≤ j ≤ n. Thus, a typical fixed-level edge in H_{pn}^{Λ} − W is ((i_{1}, j), (i_{2}, j)) where i_{1} ≠ i_{2}, and j ≠ w_{i_{1}} and j ≠ w_{i_{2}}, (because the vertices (i_{1}, w_{i_{1}}) and (i_{2}, w_{i_{2}}) have been removed). Without loss of generality let w_{i_{1}} ≤ w_{i_{2}}.

Now we check that ϕ maps two adjacent vertices at level j in H_{pn}^{Λ} − W onto two adjacent vertices in H_{p(n−1)}^{Λ}. There are three cases to consider:

(a) 1 ≤ j < w_{i_{1}} ≤ w_{i_{2}} ≤ n. Then ϕ((i_{1}, j), (i_{2}, j)) = (ϕ(i_{1}, j), ϕ(i_{2}, j)) = ((i_{1}, j), (i_{2}, j)), which is certainly a (fixed-level) edge in H_{p(n−1)}^{Λ}.

(b) 1 ≤ w_{i_{1}} < j < w_{i_{2}} ≤ n. Then ϕ((i_{1}, j), (i_{2}, j)) = ((i_{1}, j − 1), (i_{2}, j)). Now w_{i_{1}} < w_{i_{2}} and ((i_{1}, w_{i_{1}}), (i_{2}, w_{i_{2}})) is an edge in W, and so in H_{pn}^{Λ}, so i_{1} ∈ Λ_{i_{2}}; and 1 ≤ j − 1 < j ≤ n − 1 and so ((i_{1}, j − 1), (i_{2}, j)) is a (cross-level) edge in H_{p(n−1)}^{Λ}.

(c) 1 ≤ w_{i_{1}} ≤ w_{i_{2}} < j ≤ n. Then ϕ((i_{1}, j), (i_{2}, j)) = ((i_{1}, j − 1), (i_{2}, j − 1)), which, again, is a fixed-level edge in H_{p(n−1)}^{Λ}.

Cross-level edges in H_{pn}^{Λ} are of the form ((i, j), (i′, j′)) where j > j′ and i′ ∈ Λ_{i}. Thus cross-level edges in H_{pn}^{Λ} − W are of the form ((i, j), (i′, j′)), where j > j′, j ≠ w_{i}, j′ ≠ w_{i′}, and i′ ∈ Λ_{i}.

Now we check that ϕ maps two adjacent vertices at levels j and j′ in H_{pn}^{Λ} − W onto two adjacent vertices in H_{p(n−1)}^{Λ}. There are four cases to consider:

(a) 1 ≤ j < w_{i} ≤ n and 1 ≤ j′ < w_{i′} ≤ n. Then ϕ((i, j), (i′, j′)) = ((i, j), (i′, j′)), a cross-level edge in H_{p(n−1)}^{Λ}.

(b) 1 ≤ j < w_{i} ≤ n and 1 ≤ w_{i′} < j′ ≤ n. Then ϕ((i, j), (i′, j′)) = ((i, j), (i′, j′ − 1)), again, a cross-level edge in H_{p(n−1)}^{Λ}.

(c) 1 ≤ w_{i} < j ≤ n and 1 ≤ j′ < w_{i′} ≤ n. Then ϕ((i, j), (i′, j′)) = ((i, j − 1), (i′, j′)); here j − 1 ≥ j′. If j − 1 > j′ then this is a cross-level edge in H_{p(n−1)}^{Λ}, or, if j − 1 = j′, then this is a fixed-level edge in H_{p(n−1)}^{Λ}.

(d) 1 ≤ w_{i} < j ≤ n and 1 ≤ w_{i′} < j′ ≤ n. Then ϕ((i, j), (i′, j′)) = ((i, j − 1), (i′, j′ − 1)), a cross-level edge in H_{p(n−1)}^{Λ}.

Thus ϕ moves edges in H_{pn}^{Λ} − W to edges in H_{p(n−1)}^{Λ}.

Now, from Lemma 2.1, the graphs H_{pn}^{Λ} − W and H_{p(n−1)}^{Λ} have the same number of edges, and so ϕ is an isomorphism.

Thus we have the following existence result for K_{p}-removable sequences:

Theorem 2.3 Let Λ be uniform. For any p ≥ 3 the sequence {H_{pn}^{Λ}} is K_{p}-removable.

Proof. By construction, for every n ≥ 1, the graph H_{pn}^{Λ} has pn vertices. Clearly the sequence {H_{pn}^{Λ}} satisfies A1, and, from Lemma 2.2, it satisfies A2, hence it is K_{p}-removable.

Example 1 p = 3, Λ_{1} = {2}, Λ_{2} = {1, 3}, Λ_{3} = {2}. Here Λ = (Λ_{1}, Λ_{2}, Λ_{3}) is uniform with λ_{1} = μ_{1} = 1, λ_{2} = μ_{2} = 2, and λ_{3} = μ_{3} = 1. The first 3 graphs in the K_{3}-removable sequence {H_{3n}^{Λ}} are shown in Fig. 1.

The converse of Theorem 2.3 is not true, consider the example: Example 2 p = 3, Λ_{1} = {2}, Λ_{2} = Λ_{3} = ∅. Here Λ = (Λ_{1}, Λ_{2}, Λ_{3}), and it is straightforward to show that {H_{3n}^{Λ}} is K_{3}-removable but λ_{1} = 1 and μ_{1} = 0, and so λ_{1} ≠ μ_{1} and Λ is not uniform.

We call a K_{p}-removable sequence {G_{pn}} regular if all graphs in the sequence are regular, and irregular if at least one graph in the sequence is irregular.

•  •  • •  •  • •  •  • (1, 1)  (2, 1)  (3, 1) (1, 2)  (2, 2)  (3, 2) (1, 3)  (2, 3)  (3, 3)

•  •  • •  •  • (1, 1)  (2, 1)  (3, 1) (1, 2)  (2, 2)  (3, 2) •  •  • (1, 1)  (2, 1)  (3, 1)

Figure 1: The first 3 graphs in the irregular K_{3}-removable sequence {H_{3n}^{Λ}} where Λ = {Λ_{1}, Λ_{2}, Λ_{3}} with Λ_{1} = {2}, Λ_{2} = {1, 3}, and Λ_{3} = {2}. See Examples 1 and 3.

In Section 3 we show that all K_{p}-removable sequences for p = 1 and p = 2 are regular. As the next example shows, an irregular K_{p}-removable sequence exists for every p ≥ 3. Example 3 For a fixed p ≥ 3, Λ_{1} = {2}, Λ_{2} = {1, 3}, Λ_{3} = {2}, and Λ_{i} = ∅ for 4 ≤ i ≤ p. Then Λ = (Λ_{1}, …, Λ_{p}) is uniform and so {H_{pn}^{Λ}} is K_{p}-removable. Moreover, {H_{pn}^{Λ}} is irregular because H_{p2}^{Λ} is irregular: deg((1, 2)) = p but deg((2, 2)) = p+1. See Fig. 1 where p = 3, deg((1, 2)) = 3 but deg((2, 2)) = 4.

We are interested in the K_{p}’s in H_{pn}^{Λ}. The next theorem gives necessary and sufficient conditions for their existence.

Let V = H_{pn}^{Λ}[(1, v_{1}), …, (p, v_{p})] be an arbitrary induced subgraph in H_{pn}^{Λ} with exactly one vertex from each independent set I_{i}. Let V have vertices at m different levels: ℓ_{1}, …, ℓ_{m} where ℓ_{1} < ⋯ < ℓ_{m}. For 1 ≤ k ≤ m, let V_{k} = {i | v_{i} = ℓ_{k}} ≠ ∅ be the set of first coordinates of all vertices of V at level ℓ_{k} . Then the sets V_{1}, …, V_{m} partition [p] = {1, …, p}, and:

Theorem 2.4 With the above notation V = K_{p} if and only if for every k, with 1 ≤ k ≤ m, we have

V_{1} ∪ ⋯ ∪ V_{k} = ∩_{i∈V_{k+1}∪···∪V_{m}} Λ_{i},

where we define ∩_{i∈∅} Λ_{i} = [p].

Proof. Suppose that V = K_{p}, and suppose i′ ∈ V_{1} ∪ ⋯ ∪ V_{k} for some k with 1 ≤ k ≤ m. Now vertex (i′, v_{i′}) is at a lower level than all vertices (i, v_{i}) where i ∈ V_{k+1} ∪ ⋯ ∪ V_{m}, so i′ ∈ Λ_{i} for all i ∈ V_{k+1} ∪ ⋯ ∪ V_{m}. Thus i′ ∈ ∩_{i∈V_{k+1}∪···∪V_{m}} Λ_{i}, and V_{1} ∪ ⋯ ∪ V_{k} ⊆ ∩_{i∈V_{k+1}∪···∪V_{m}} Λ_{i}. But, because, i ∉ Λ_{i}, we have ∩_{i∈V_{k+1}∪···∪V_{m}} Λ_{i} ⊆ [p]\{V_{k+1} ∪ ⋯ ∪ V_{m}} = V_{1} ∪ ⋯ ∪ V_{k}. Hence V_{1} ∪ ⋯ ∪ V_{k} = ∩_{i∈V_{j+1}∪···∪V_{m}} Λ_{i}, as required. The converse is straightforward.

Example 4 See Example 1 and Fig. 1. Here p = 3, Λ_{1} = {2}, Λ_{2} = {1, 3}, and Λ_{3} = {2}. Consider the induced graph H_{33}^{Λ}[(1, 1), (2, 3), (3, 1)] = K_{3}. This K_{3} has vertices at m = 2 levels, i.e., at level ℓ_{1} = 1 and at level ℓ_{2} = 3, so V_{1} = {1, 3} and V_{2} = {2}. For k = 1 we have

V_{1} = ∩_{i∈V_{2}}Λ_{i} = Λ_{2},

and for k = 2

V_{1} ∪ V_{2} = ∩_{i∈∅}Λ_{i} = [3] = {1, 2, 3}.

Such a K_{p} with vertices at more than one level is a cross-level K_{p}.

3 Regular sequences, uniqueness of (K_{p}, λ)- removable sequences for λ = 0, p − 1, or p

Here we consider regular K_{p}-removable sequences {G_{pn}}, i.e., those which also satisfy:

A3 G_{pn} is regular for every n ≥ 1.

For such a sequence we use the notation {R_{pn}}, for every n ≥ 1 R_{pn} is regular of degree deg(R_{pn}). We know that R_{p1} = K_{p}, and the second graph in this sequence is R_{p2}, so let us define λ by

λ = deg(R_{p2}) − deg(R_{p1}) = deg(R_{p2}) − (p − 1).  (3)

Lemma 3.1 For a fixed p ≥ 1 let {R_{pn}} be K_{p}-removable with λ defined as above. Then

(i) 0 ≤ λ ≤ p, (ii) deg(R_{pn}) = λ(n − 1) + p − 1 for every n ≥ 1, (iii) λ = deg(R_{pn}) − deg(R_{p(n−1)}) for every n ≥ 2.

Proof. (i) By A1 and A2 the graph R_{p2} contains a K_{p} with R_{p2} − K_{p} = R_{p1} = K_{p}. By A3 R_{p2} is regular and deg(R_{p2}) ≥ deg(K_{p}) = p − 1, and so λ = deg(R_{p2}) − (p − 1) ≥ 0. Also, deg(R_{p2}) ≤ deg(R_{p1}) + p because the degree of a vertex in R_{p1} can be increased by at most p when constructing R_{p2} (if it is made adjacent to each of the p vertices in the new K_{p}), hence λ ≤ p. Thus 0 ≤ λ ≤ p, i.e., λ = 0, …, p. (ii) Here we use induction on n. For n = 1 (ii) is true by A1, and for n = 2 it is true by (3). So assume that n ≥ 3 and that (ii) is true for n − 1, i.e., for the graph R_{p(n−1)}. Now R_{pn} is obtained from R_{p(n−1)} by adding on a new K_{p} and some cross-level edges between them. But R_{pn} is regular, so we can count these cross-level edges in two different ways:

(n − 1)p [deg(R_{pn}) − deg(R_{p(n−1)})] = p [deg(R_{pn}) − (p − 1)].

This gives

deg(R_{pn}) = \frac{(n − 1)deg(R_{p(n−1)}) − (p − 1)}{n − 2}
= λ(n − 1) + p − 1,

using the induction hypothesis. Thus the induction goes through and (ii) is true for every n ≥ 1. (iii) This follows directly from (ii).

For a fixed p ≥ 1 and a fixed λ where λ = 0, …, p, let {R_{pn}} be a K_{p}- removable sequence in which deg(R_{pn}) = λ(n−1)+p−1 for every n ≥ 1. We call the sequence {R_{pn}} regular (K_{p}, λ)-removable, and denote it by {R_{pn}^{λ}}. Lemma 3.1(iii) then says that

λ = deg(R_{pn}^{λ}) − deg(R_{p(n−1)}^{λ}) for every n ≥ 2,  (4)

i.e., as we move from R_{p(n−1)}^{λ} to R_{pn}^{λ} in the sequence {R_{pn}^{λ}}, the degree of regularity always increases by λ.

Now we look at some small values of p.

Example 5 p = 1, so deg(R_{1n}^{λ}) = λ(n − 1) where λ = 0 or 1.

λ = 0 Here deg(R_{1n}^{0}) = 0. So R_{1n}^{0} is the graph with n isolated vertices, nK_{1}. Clearly R_{11}^{0} = K_{1} and, for n ≥ 2, the removal of any K_{1} from nK_{1} gives the graph (n − 1)K_{1}, thus {R_{1n}^{0}} = {nK_{1}} is K_{1}-removable. It is also clear that {nK_{1}} is the unique regular (K_{1}, 0)-removable sequence.

λ = 1 Here deg(R_{1n}^{1}) = n − 1. {R_{1n}^{1}} = {K_{n}} is the unique regular (K_{1}, 1)- removable sequence.

Example 6 p = 2, so deg(R_{2n}^{λ}) = λ(n − 1) + 1 where λ = 0, 1, or 2.

λ = 0 Here deg(R_{2n}^{0}) = 1. {R_{2n}^{0}} = {nK_{2}} is the unique regular (K_{2}, 0)- removable sequence.

λ = 1 Here deg(R_{2n}^{1}) = n. Now K_{n,n}, the complete bipartite graph on 2n vertices, has degree n. Also K_{1,1} = K_{2} and, for every n ≥ 2, the removal of any K_{2} from K_{n,n} results in K_{n−1,n−1}, i.e. K_{n,n} − K_{2} = K_{n−1,n−1}. So one example of a regular (K_{2}, 1)-removable sequence is {R_{2n}^{1}} = {K_{n,n}}, we show in Corollary 3.2 that this is the unique example.

\begin{matrix}n = 3 & 3K_{2} & K_{3,3} & K_{2·3} = K_{6} \\ n = 2 & 2K_{2} & K_{2,2} & K_{2·2} = K_{4} \\ n = 1 & \begin{matrix}\{nK_{2}\} \\ λ = 0 \end{matrix} & 1K_{2} = K_{1,1} = K_{2·1} \{K_{n,n}\} λ = 1 & \begin{matrix}\{K_{2n}\} \\ λ = 2 \end{matrix} \end{matrix}

Figure 2: The first 3 graphs in each of the K_{2}-removable sequences {nK_{2}}, {K_{n,n}}, and {K_{2n}}. These are the unique regular (K_{2}, 0)-, (K_{2}, 1)-, and (K_{2}, 2)-removable sequences, respectively. See Example 6.

λ = 2 Here deg(R_{2n}^{2}) = 2n−1. {R_{2n}^{2}} = {K_{2n}} is the unique regular (K_{2}, 2)- removable sequence.

We see that the 1-st graph in each of the three sequences {R_{2n}^{0}} = {nK_{2}}, {R_{2n}^{1}} = {K_{n,n}}, and {R_{2n}^{2}} = {K_{2n}} is K_{2}, i.e. we must think of K_{2} as being the three graphs 1K_{2} = K_{1,1} = K_{2·1}. Then the 2-nd graph in each sequence is obtained by changing the 1’s in the notation for these graphs into 2’s, etc. This is illustrated in Fig. 2, where the first 3 graphs in each of the three sequences {nK_{2}}, {K_{n,n}}, and {K_{2n}} are shown. Note also that the n-th graphs in each of the three sequences are well-known graphs on 2n vertices: nK_{2}, K_{n,n}, and K_{2n}, respectively.

Recall that a K_{p}-removable sequence {G_{pn}} is regular if all of its graphs are regular, and is irregular if at least one of its graphs is irregular. The next result shows that all K_{p}-removable sequences for p = 1 or p = 2 are regular (and are those given in Examples 5 and 6). From Example 3 we see that irregular K_{p}-removable sequences exist for every p ≥ 3.

Corollary 3.2 For p = 1 or p = 2 all K_{p}-removable sequences are regular, (and are given in Examples 5 and 6).

Proof. (p = 2) Let {G_{2n}} be a K_{2}-removable sequence, then G_{21} = K_{2}. A candidate for G_{22} must be a graph on 4 vertices with at least two disjoint K_{2}’s, and the removal of any K_{2} must leave a K_{2}. The only possibilities are:

(a) 2K_{2}, (b) K_{2,2}, or (c) K_{2·2} = K_{4}, all of which are regular.

(a) We prove by induction on n that if {G_{2n}} is an arbitrary K_{2}-removable sequence which begins {K_{2}, 2K_{2}, …} then it is the regular sequence {nK_{2}}.

Let n ≥ 3 and suppose that G_{2(n−1)} = (n − 1)K_{2}. Now consider G_{2n} which is the union of (n − 1)K_{2} and a ‘new’ K_{2} (and some edges between them); let edge (u, v) be this new K_{2}. If (u, v) is an isolated K_{2} then we are finished, so, assume that u is adjacent to vertex u_{1} in G_{2(n−1)}. Now G_{2(n−1)} = (n − 1)K_{2} and n ≥ 3 so G_{2(n−1)} contains some edge (u_{2}, u_{3}) with u_{2} ≠ u_{1} and u_{3} ≠ u_{1}. But G_{2n} − (u_{2}, u_{3}) contains the path on the three vertices u_{1}, u, and v (or triangle if (v, u_{1}) is also an edge); a contradiction because G_{2n} − (u_{2}, u_{3}) = (n − 1)K_{2}. Thus (u, v) must be an isolated K_{2} and the induction goes through, i.e., G_{2n} = nK_{2} and so {G_{2n}} = {nK_{2}}.

(b) Similarly we use induction to show that any K_{2}-removable sequence {G_{2n}} which begins {K_{2} = K_{1,1}, K_{2,2}, …} is the regular sequence {K_{n,n}}.

Let n ≥ 3 and suppose that G_{2(n−1)} = K_{n−1,n−1}; let the 2 independent sets of G_{2(n−1)} be I_{1} = {u_{1}, …, u_{n−1}} and I_{2} = {v_{1}, …, v_{n−1}}, and let the new K_{2} of G_{2n} be the edge (u, v). Now (u, v) cannot be isolated so let vertex u be adjacent to some vertices in G_{2(n−1)}. Suppose that u is adjacent to vertex u_{j_{1}} ∈ I_{1} and to vertex v_{j_{2}} ∈ I_{2}, then G_{2n}[u, u_{j_{1}}, v_{j_{2}}] = C_{3}, an odd cycle. Now remove any K_{2} = (u_{j_{3}}, v_{j_{4}}) where j_{3} ≠ j_{1} and j_{4} ≠ j_{2}, then G_{2n} − (u_{j_{3}}, v_{j_{4}}) = K_{n−1,n−1} still contains this odd cycle, a contradiction. Thus u is adjacent to vertices from exactly one of I_{1} or I_{2}, say I_{2}.

Now suppose that u is not adjacent to every vertex in I_{2}, suppose that it is not adjacent to v_{j_{5}}, say. Consider the edge (u_{1}, v_{j_{6}}) where j_{6} ≠ j_{5}. In the graph G_{2n} − (u_{1}, v_{j_{6}}) = K_{n−1,n−1} the set of vertices {u_{2}, …, u_{n−1}, u} = {I_{1} ∪ {u}}\{u_{1}} is one of the independent sets and {I_{2} ∪ {v}}\{v_{j_{6}}} is the other. Thus (u, v_{j_{5}}) is an edge, a contradiction. So u is adjacent to all vertices in I_{2}. Similarly v is adjacent to all vertices in I_{1}. Thus G_{2n} = K_{n,n} and {G_{2n}} = {K_{n,n}}.

The proofs for (c) K_{2·2} = K_{4} and the case p = 1 are similar.

Before the next main result, Theorem 3.4, we need:

Lemma 3.3 For a fixed p ≥ 1 let {R_{pn}^{λ}} be regular (K_{p}, λ)-removable. Then, for every n ≥ 1,

(i) R_{pn}^{λ} contains ≥ n disjoint K_{p}’s, (ii) R_{pn}^{λ} contains no K_{p+1}’s for 0 ≤ λ ≤ p − 1.

Proof. (i) See the first paragraph of Section 2. (ii) Let 0 ≤ λ ≤ p − 1. Suppose that for some p + 1 vertices {v_{1}, …, v_{p+1}} of R_{pn}^{λ} we have R_{pn}^{λ}[v_{1}, …, v_{p+1}] = K_{p+1}. Consider R_{pn}^{λ} − K_{p} where K_{p} = R_{pn}^{λ}[v_{1}, …, v_{p}]. Clearly v_{p+1} ∈ R_{pn}^{λ} − K_{p} and deg(v_{p+1}) has decreased by p; but from (4) it should have decreased by λ, a contradiction because 0 ≤ λ ≤ p − 1.

Recall that K_{p×n} = K\underbrace{n,...,n}_{p} denotes the complete p -partite graph on pn

vertices.

Theorem 3.4 For a fixed p ≥ 2 there is a unique regular (K_{p}, λ)-removable sequence for λ = 0, p − 1, or p:

(i) {nK_{p}} is the unique regular (K_{p}, 0)-removable sequence, (ii) {K_{p×n}} is the unique regular (K_{p}, p − 1)-removable sequence, (iii) {K_{pn}} is the unique regular (K_{p}, p)-removable sequence.

Proof. The proofs of (i) and (iii) are straightforward. (ii) (λ = p − 1) We use induction on n. Let {R_{pn}^{p−1}} be an arbitrary regular (K_{p}, p − 1)-removable sequence; for n = 1 we know that R_{p1}^{p−1} = K_{p} = K_{p×1}. Let n ≥ 2, then R_{pn}^{p−1} contains a K_{p} = R_{pn}^{p−1}[v_{1}, …, v_{p}], say. By the induction hypothesis we have R_{pn}^{p−1} − K_{p} = R_{p(n−1)}^{p−1} = K_{p×(n−1)}. Let I_{1}, …, I_{p} be the p independent sets of R_{p(n−1)}^{p−1}, each has n−1 vertices. Now suppose that in R_{pn}^{p−1} a vertex from {v_{1}, …, v_{p}}, say v_{i}, is adjacent to a vertex from each of these p independent sets; call these vertices {u_{1}, …, u_{p}}, where u_{k} ∈ I_{k} for k = 1, …, p. Then R_{pn}^{p−1}[v_{i}, u_{1}, …, u_{p}] = K_{p+1}, a contradiction to Lemma 3.3(ii). Thus v_{i} is adjacent to vertices in at most p − 1 of the independent sets I_{1}, …, I_{p}.

Now v_{i} is adjacent to (p − 1)(n − 1) vertices from I_{1} ∪ ⋯ ∪ I_{p}, so it must be adjacent to all n − 1 vertices in some p − 1 of I_{1}, …, I_{p}. Suppose that in R_{pn}^{p−1} two distinct vertices from {v_{1}, …, v_{p}}, say v_{i_{1}} and v_{i_{2}}, are adjacent to all of the vertices in the same p − 1 independent sets, say I_{1}, …, I_{p−1}. Let u_{k} ∈ I_{k} for k = 1, …, p − 1. Then R_{pn}^{p−1}[v_{i_{1}}, v_{i_{2}}, u_{1}, …, u_{p−1}] = K_{p+1}, again a contradiction. Thus, any two distinct vertices from {v_{1}, …, v_{p}} are adjacent to all vertices in distinct (p − 1)-sets of {I_{1}, …, I_{p}}.

For i = 1, …, p let v_{i} be non-adjacent to all vertices in the independent set I_{i′} for some i′ = 1, …, p. By above the mapping v_{i} ↔ I_{i′} is a bijection. Then {v_{i}} ∪ I_{i′} is an independent set in R_{pn}^{p−1}, and v_{i} is adjacent to all the vertices in all other independent sets. This is true for every i = 1, …, p. It is now clear that R_{pn}^{p−1} = K_{p×n}, and so the induction goes through and {R_{pn}^{p−1}} = {K_{p×n}}.

Note that this theorem connects three well-known graphs on pn vertices: nK_{p}, K_{p×n}, and K_{pn}. The case p = 2 was discussed in Example 6 and illustrated in Fig. 2. Note also that the three regular sequences (i) {nK_{p}}, (ii) \{K_{p×n}\}, and (iii) \{K_{pn}\} are the sequences \{H_{pn}^{Λ}\} where (i) Λ = (\underbrace{∅, …, ∅}_{p}),

(ii) Λ = ([p]\{1}, …, [p]\{p}), and (iii) Λ = ([p], …, [p]), respectively. (In (iii) Λ is not uniform.)

So, for p = 1 or p = 2 and all values of λ, and for every p ≥ 3 and λ = 0, p − 1, or p, there is a unique regular (K_{p}, λ)-removable sequence.

4 Levelled Cayley Graphs, more regular (K_{p}, λ)- removable sequences

Generally our construction of {H_{pn}^{Λ}} from Section 2 gives irregular sequences. For an arbitrary vertex (i, j) ∈ H_{pn}^{Λ} we have deg((i, j)) = λ_{i}(n − 1) + p − 1, see (2). So H_{pn}^{Λ} is regular if and only if λ_{i} is constant for all i ∈ [p]. We set λ_{i} = λ then H_{pn}^{Λ} is regular of degree λ(n − 1) + p − 1, (see Lemma 3.1(ii)), and {H_{pn}^{Λ}} is a regular (K_{p}, λ)-removable sequence.

We now construct a regular (K_{p}, λ)-removable sequence using a finite group. This combines the construction of {H_{pn}^{Λ}} from Section 2 with the construction of a Cayley graph; see, for example, p. 122 of Biggs [2].

Let p ≥ 3 and let G_{p} = {g_{1}, …, g_{p}} be a finite group with p elements, where g_{1} = e is the identity element. Let Λ ⊆ G_{p} be a subset of G_{p} with e ∉ Λ and |Λ| = λ.

Now consider the following graph, a levelled Cayley graph, Γ_{n} = Γ_{n}(G_{p}, Λ): It has n ≥ 1 levels of vertices, each level having p vertices. For any fixed j with 1 ≤ j ≤ n the vertices at level j are {(g_{1}, j), …, (g_{p}, j)} = {(g, j) | g ∈ G_{p}}, and the edges are of two types:

(i) fixed-level edges, say at level j

((g, j), (h, j)) is an edge for all g, h ∈ G_{p} where g ≠ h;

(i.e., the ‘fixed-level’ graph is K_{p}), and (ii) cross-level edges, for j > j′

((g, j), (g′, j′)) is an edge if and only if g′g^{−1} ∈ Λ.

Using Theorem 2.3 it is straightforward to prove:

Theorem 4.1 For any finite group G_{p} with p elements and any Λ ⊆ G_{p} with e ∉ Λ and |Λ| = λ, the sequence {Γ_{n}(G_{p}, Λ)} is regular (K_{p}, λ)-removable.

Now, for any G_{p} with p ≥ 3 and for each λ = 0, …, p − 1, there exists a Λ satisfying the requirements in Theorem 4.1, and Theorem 3.4(iii) takes care of λ = p, so we have the following existence result for regular (K_{p}, λ)-removable sequences.

Theorem 4.2 For any p ≥ 3 and any λ = 0, …, p, there exists a regular (K_{p}, λ)-removable sequence, namely the sequence {Γ_{n}(G_{p}, Λ)}, where G_{p} is any finite group of order p and Λ is any subset of G_{p} with e ∉ Λ and |Λ| = λ.

Let \overline{Λ} denote the complement of Λ in G_{p} and let ⟨\overline{Λ}⟩ be the subgroup generated by \overline{Λ}, also let ⟨\overline{Λ}⟩g denote a typical coset of this subgroup.

Let V = Γ_{n}[(g_{1}, v_{1}), …, (g_{p}, v_{p})] be an arbitrary induced subgraph in Γ_{n}(G_{p}, Λ) with exactly one vertex from each independent set I_{i} = {(g_{i}, j) | 1 ≤ j ≤ n}, where i = 1, …, p. We are interested in the K_{p}’s in Γ_{n}(G_{p}, Λ). The next theorem gives a necessary and sufficient condition for this V to be a K_{p}, this condition is cleaner than the corresponding condition of Theorem 2.4 for the graph H_{pn}^{Λ}; it also enables us to count the number of K_{p}’s in Γ_{n}(G_{p}, Λ).

As in Section 2 let V have vertices at m different levels: ℓ_{1} < ⋯ < ℓ_{m}. For 1 ≤ k ≤ m, let V_{k} = {g_{i} | v_{i} = ℓ_{k}} ≠ ∅ be the set of first coordinates of all vertices of V at level ℓ_{k}. Then the sets V_{1}, …, V_{m} partition G_{p}, and we have:

Theorem 4.3 With the above notation V = K_{p} if and only if for every k, with 1 ≤ k ≤ m, V_{k} is a union of cosets of ⟨\overline{Λ}⟩.

Proof. Suppose that V = Γ_{n}[(g_{1}, v_{1}), …, (g_{p}, v_{p})] = K_{p}. Now ℓ_{m} = max{v_{1}, …, v_{p}} is the highest level of Γ_{n}(G_{p}, Λ) which contains vertices from V, and V_{m} = {g_{i} | v_{i} = ℓ_{m}} is the set of first coordinates of all vertices of V at this highest level.

Let s be an arbitrary element in V_{m} ⊆ G_{p}. Now consider the graph V′ = Γ_{n}[(g_{1}s^{−1}, v_{1}), …, (g_{p}s^{−1}, v_{p})], let us reorder the vertices in V′ so that V′ = Γ_{n}[(g_{1}, v′_{1}), …, (g_{p}, v′_{p})]; we use this version of V′. The graph V′ is also a K_{p} and the highest level of its vertices is ℓ_{m} also. Then V′_{m} = {g_{i} | v′_{i} = ℓ_{m}} = V_{m}s^{−1} is the set of first coordinates of these vertices. We show that V′_{m} is a union of cosets of ⟨\overline{Λ}⟩.

First we show that \overline{Λ} ⊆ V′_{m}. Now g_{1} = e ∈ \overline{Λ} and s ∈ V_{m}, so certainly e = ss^{−1} ∈ V′_{m}. So vertex (g_{1}, v′_{1}) = (e, ℓ_{m}) ∈ V′ lies at level ℓ_{m}. Let g_{i} ≠ e and let g_{i} ∈ \overline{Λ}, but suppose that g_{i} ∉ V′_{m}. This means that vertex (g_{i}, v′_{i}) ∈ V′ does not lie at level ℓ_{m} so it must lie at a lower level, i.e., ℓ_{m} > v′_{i}. Now, because ((e, ℓ_{m}), (g_{i}, v′_{i})) is an edge in V′ then ((s, ℓ_{m}), (g_{i}s, v′_{i})) is an edge in V and so in Γ_{n}(G_{p}, Λ); so g_{i}ss^{−1} = g_{i} ∈ Λ, a contradiction because g_{i} ∈ \overline{Λ}. Thus for every g_{i} ∈ \overline{Λ}, then g_{i} ∈ V′_{m}, i.e., \overline{Λ} ⊆ V′_{m}.

Next we show that ⟨\overline{Λ}⟩ ⊆ V′_{m}. For any r ≥ 1 let ∏(r) denote a product of r arbitrary elements from \overline{Λ}. By induction we show, for any fixed r ≥ 1, that every ∏(r) ∈ V′_{m}. Now \overline{Λ} ⊆ V′_{m}, i.e., every ∏(1) ∈ V′_{m}. Assume for some r with r ≥ 1 that every ∏(r) ∈ V′_{m}. Now suppose that some ∏(r + 1), say h(r + 1) = a_{1} ⋯ a_{r+1} ∉ V′_{m}, but each a_{1}, …, a_{r+1} ∈ \overline{Λ}. Let h(r) = a_{2} ⋯ a_{r+1}, then, by the induction hypothesis, h(r) ∈ V′_{m} so vertex (h(r), ℓ_{m}) ∈ V′ is at the highest level ℓ_{m} and the vertex in V′ with first coordinate h(r + 1) is at a lower level. There is an edge between these two vertices so h(r + 1)h(r)^{−1} = a_{1} ∈ Λ, a contradiction because a_{1} ∈ \overline{Λ}. Thus h(r + 1) ∈ V′_{m} and the induction goes through, and so ⟨\overline{Λ}⟩ ⊆ V′_{m}.

Finally we show that V′_{m} is a union of cosets of ⟨\overline{Λ}⟩. Let g ∈ V′_{m}, but suppose that g ∉ ⟨\overline{Λ}⟩. Then, by similar reasoning to before, we see that every ∏(1)g ∈ V′_{m}, and by induction, that every ∏(r)g ∈ V′_{m} for every r ≥ 1; thus the coset ⟨\overline{Λ}⟩g ⊆ V′_{m}. Thus V′_{m} is a union of cosets of ⟨\overline{Λ}⟩, and so V_{m} = V′_{m}s is also.

Now we return to the graph V and show that V_{k} is a union of cosets of ⟨\overline{Λ}⟩ for every 1 ≤ k ≤ m. From above this is true for V_{m}, so assume for all k with k ≤ m that V_{k} is a union of cosets of ⟨\overline{Λ}⟩, we show that V_{k−1} is also.

Let g ∈ V_{k−1}, we show that the coset ⟨\overline{Λ}⟩g ⊆ V_{k−1}. As before first we show that every ∏(1)g ∈ V_{k−1}, for, suppose not, then: Either ∏(1)g ∈ V_{k′} where k′ > k − 1, so, by the induction hypothesis, V_{k′} is a union of cosets of ⟨\overline{Λ}⟩. Thus ⟨\overline{Λ}⟩ ∏(1)g = ⟨\overline{Λ}⟩g ⊆ V_{k′}, so g ∈ V_{k′}, a contradiction because g ∈ V_{k−1}; Or ∏(1)g ∈ V_{k′} where k′ < k − 1, i.e., level ℓ_{k′} is lower than level ℓ_{k−1}. So vertex (∏(1)g, ℓ_{k′}) ∈ V is at a lower level than vertex (g, ℓ_{k−1}) ∈ V, so ∏(1)gg^{−1} = ∏(1) ∈ Λ, again a contradiction. So ∏(1)g ∈ V_{k−1}, and we proceed by induction as before to show that for any r ≥ 1 then every ∏(r)g ∈ V_{k−1} and so ⟨\overline{Λ}⟩g ⊆ V_{k−1}, and the induction on k goes through; thus V_{k−1} is a union of cosets of ⟨\overline{Λ}⟩.

So, in conclusion, for any k with 1 ≤ k ≤ m, V_{k} is a union of cosets of ⟨\overline{Λ}⟩, as required.

For the converse let each V_{k} be a union of cosets of ⟨\overline{Λ}⟩. Let (g, ℓ_{k}) and (g′, ℓ_{k′}) be two arbitrary vertices in V, we show that ((g, ℓ_{k}), (g′, ℓ_{k′})) is an edge in Γ_{n}(G_{p}, Λ). If ℓ_{k} = ℓ_{k′} then, certainly, ((g, ℓ_{k}), (g′, ℓ_{k′})) is an edge by construction of Γ_{n}(G_{p}, Λ). Otherwise, without loss of generality, let ℓ_{k} > ℓ_{k′}. Then g and g′ are in different cosets of ⟨\overline{Λ}⟩, so g′g^{−1} ∉ ⟨\overline{Λ}⟩, so g′g^{−1} ∈ \overline{⟨\overline{Λ}⟩} ⊆ Λ, and again ((g, ℓ_{k}), (g′, ℓ_{k′})) is an edge. Thus V = K_{p} as required.

Now we count the number of K_{p}’s in Γ_{n}(G_{p}, Λ); let |G_{p} : ⟨\overline{Λ}⟩| be the index of ⟨\overline{Λ}⟩ in G_{p}, i.e., the number of cosets of ⟨\overline{Λ}⟩ in G_{p}.

Corollary 4.4 The number of K_{p}’s in Γ_{n}(G_{p}, Λ) is given by

n^{|G_{p}:⟨\overline{Λ}⟩|}.

Proof. Consider any coset ⟨\overline{Λ}⟩g, let us ‘place’ the elements of this coset at any fixed level j, where 1 ≤ j ≤ n, in the graph Γ_{n}(G_{p}, Λ). Each such placement of every coset of ⟨\overline{Λ}⟩ gives a K_{p} and every K_{p} corresponds to such a placement of every coset of ⟨\overline{Λ}⟩. Hence, the number of K_{p}’s in Γ_{n}(G_{p}, Λ) equals the number of such placements of all the cosets of ⟨\overline{Λ}⟩. There are |G_{p} : ⟨\overline{Λ}⟩| cosets, and n levels to place each, hence n^{|G_{p}:⟨\overline{Λ}⟩|} such placements and so n^{|G_{p}:⟨\overline{Λ}⟩|} corresponding K_{p}’s.

Example 7 (a) Let Sym(3) = {e, (12), (13), (23), (123), (132)} be the symmetric group on \{1, 2, 3\}, and let Λ = \{(12), (13), (23), (123)\}. Then \overline{Λ} = \{e, (132)\} and ⟨\overline{Λ}⟩ = \{e, (123), (132)\}; the other coset of ⟨\overline{Λ}⟩ is ⟨\overline{Λ}⟩(12) = {(12), (13), (23)}. Consider the graph Γ_{2}(Sym(3), Λ) shown in Fig. 3(a), we have |Sym(3) : ⟨\overline{Λ}⟩| = 2 so this graph has 2^{2} = 4 K_{6}’s. They are the 2 fixed-level K_{6}’s, Γ_{2}[(e, 1), ((123), 1), ((132), 1), ((12), 2), ((13), 2), ((23), 2)], and Γ_{2}[(e, 2), ((123), 2), ((132), 2), ((12), 1), ((13), 1), ((23), 1)]. This is the 2nd graph in the regular (K_{6}, 4)-removable sequence {Γ_{n}(Sym(3), Λ)}.

(b) Let ℤ_{6} = {0, 1, 2, 3, 4, 5} be the additive group (mod 6), and let Λ = \{1, 2, 4, 5\}. Then Λ = ⟨\overline{Λ}⟩ = \{0, 3\} and the other cosets of ⟨\overline{Λ}⟩ are \{1, 4\} and \{2, 5\}. Thus |ℤ_{6} : ⟨\overline{Λ}⟩| = 3 and Γ_{2}(ℤ_{6}, Λ) has 2^{3} = 8 K_{6}’s, see Fig. 3(b). One such K_{6} is Γ_{2}[(0, 2), (3, 2), (1, 1), (4, 1), (2, 1), (5, 1)], and another is Γ_{2}[(0, 2), (3, 2), (1, 1), (4, 1), (2, 2), (5, 2)], in which the vertices corresponding to coset {2, 5} have been moved up one level. This is the 2-nd graph in the regular (K_{6}, 4)-removable sequence {Γ_{n}(ℤ_{6}, Λ)}.

Note that the two graphs in Example 7 are non-isomorphic because they have a different number of K_{6}’s, they are the 2-nd graphs in two different regular (K_{6}, 4)-removable sequences. So, in general, regular (K_{p}, p − 2)- removable sequences are not unique.

(e, 2) ((12), 2) ((13), 2)((23), 2)((123), 2) ((132), 2) (e, 1) ((12), 1)((13), 1)((23), 1) ((123), 1)((132), 1) (a)

(0, 2) (1, 2) (2, 2) (3, 2) (4, 2) (5, 2) (0, 1)  (1, 1) (2, 1) (3, 1) (4, 1)  (5, 1) (b)

Figure 3: The non-isomorphic graphs (a) Γ_{2}(Sym(3), Λ) where Λ = {(12), (13), (23), (123)}, and (b) Γ_{2}(ℤ_{6}, Λ) where Λ = {1, 2, 4, 5}. See Example 7.

Example 8 Consider the graphs Γ_{3}(ℤ_{4}, {1}) and Γ_{3}(ℤ_{4}, {2}), shown in Figs. 4(a) and (b) respectively. Both graphs have 3 K_{4}’s. In Γ_{3}(ℤ_{4}, {1}) the union of all edges which lie outside its 3 K_{4}’s is a C_{12}, however in Γ_{3}(ℤ_{4}, {2}) this union is C_{6}∪C_{6}. Thus Γ_{3}(ℤ_{4}, {1}) ≠ Γ_{3}(ℤ_{4}, {2}) and so {Γ_{n}(ℤ_{4}, {1})} ≠ {Γ_{n}(ℤ_{4}, {2})}, and we have two different regular (K_{4}, 1)-removable sequences.

Example 8 illustrates that, in general, regular (K_{p}, 1)-removable sequences are not unique.

(0, 1)  (1, 1)  (2, 1)  (3, 1) (0, 2)  (1, 2)  (2, 2)  (3, 2) (0, 3)  (1, 3)  (2, 3)  (3, 3) (a)

(0, 1)  (1, 1)  (2, 1)  (3, 1) (0, 2)  (1, 2)  (2, 2)  (3, 2) (0, 3)  (1, 3)  (2, 3)  (3, 3) (b)

Figure 4: The non-isomorphic graphs (a) Γ_{3}(ℤ_{4}, {1}) and (b) Γ_{3}(ℤ_{4}, {2}). See Example 8.

Theorem 3.4 states that, for a fixed p ≥ 2, the only regular (K_{p}, 0)-, (K_{p}, p − 1)-, and (K_{p}, p)-removable sequences are unique. Above we give two different examples of a regular (K_{p}, 1)-removable sequence, and two different examples of a regular (K_{p}, p−2)-removable sequence; thus, in general, regular (K_{p}, λ)-removable sequences are not unique unless λ = 0, p − 1, or p.

Some final comments:

If, for some G_{p} and Λ we have |G_{p} : ⟨\overline{Λ}⟩| = 1, then the graph Γ_{n}(G_{p}, Λ) has exactly n K_{p}’s which is the least number allowed by Lemma 3.3(i). Such a graph has no cross-level K_{p}’s; e.g., Γ_{3}(ℤ_{4}, {1}) shown in Fig. 4(a).

It is also worth mentioning that for any group G_{p}: (see Theorem 3.4)

(i) {Γ_{n}(G_{p}, ∅)} = {nK_{p}} is the unique regular (K_{p}, 0)-removable sequence, (ii) {Γ_{n}(G_{p}, G_{p}\{e})} = {K_{p×n}} is the unique regular (K_{p}, p − 1)-removable sequence, (iii) {Γ_{n}(G_{p}, G_{p})} = {K_{pn}} is the unique regular (K_{p}, p)-removable sequence. (Note that in (iii) we do not have e ∉ Λ.) Thus the unique regular (K_{p}, λ)- removable sequences for λ = 0, p − 1, or p can all be constructed from an arbitrary group G_{p}.

For other papers on graph sequences see Barefoot, Entringer, and Jackson [1], and the references therein; another somewhat related paper is Duchet, Tuza, and Vestergaard [3].

We thank the referees for suggestions and comments which improved this paper.

References

[1] C.A. Barefoot, R.C. Entringer, D.E. Jackson, Graph theoretic modelling of cellular development II, Proc. 19-th Southeastern Internat. Conf. on Combinatorics, Graph Theory, and Computing, (Baton Rouge, LA, 1988), Congr. Numer. 65 (1988) 135–146.

[2] N. Biggs, Algebraic Graph Theory, 2nd Edition, (Cambridge University Press, 1993).

[3] P. Duchet, Z. Tuza, P.D. Vestergaard, Graphs in which all spanning subgraphs with r fewer edges are isomorphic, Proc. 19-th Southeastern Internat. Conf. on Combinatorics, Graph Theory, and Computing, (Baton Rouge, LA, 1988), Congr. Numer. 67 (1988) 45–57.