Generating Sequences of Clique-Symmetric Graphs via Eulerian Digraphs

John P. McSorley Dept. of CCTM London Metropolitan University 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_{p1}, G_{p2}, …} be an infinite sequence of graphs with G_{pn} having pn vertices. This sequence is called K_{p}-removable if G_{p1} ≅ K_{p}, and G_{pn} − S ≅ G_{p(n−1)} for every n ≥ 2 and every vertex subset S of G_{pn} that induces a K_{p}. Each graph in such a sequence has a high degree of symmetry: every way of removing the vertices of any fixed number of disjoint K_{p}’s yields the same subgraph. Here we construct such sequences using componentwise Eulerian digraphs as generators. The case in which each G_{pn} is regular is also studied, where Cayley digraphs based on a finite group are used. Keywords: Cayley, clique, digraph, Eulerian, reconstruction, removal, symmetric, uniform

1 K_{p}-removable sequences

In general we follow the notation in [5]. In particular, if S ⊆ V (G), let G[S] be the subgraph of G induced by S. Let p be a positive integer and n be a variable running from one to infinity. We use [p] = {1, …, p}, and i for an element in [p].

An infinite sequence of graphs {G_{pn}} = {G_{p1}, G_{p2}, …}, with G_{pn} having pn vertices, is K_{p}-removable if it satisfies the following two properties:

P1 G_{p1} ≅ K_{p},

P2 for every n ≥ 2, the graph G_{pn} contains at least one K_{p} and G_{pn} − S ≅ G_{p(n−1)} for every S for which G_{pn}[S] ≅ K_{p}.

Each graph in such a sequence has a high degree of symmetry: every way of removing the vertices of any fixed number of disjoint K_{p}’s yields the same subgraph. We call this property clique-symmetric.

We often write G = G′ in place of G ≅ G′, and refer to K_{p} as a p-clique. Let D⃗ be a digraph without loops and multiple arcs, and with vertex set

[p]. Let i⃗i′ denote an arc in A(D⃗), then i′ is an out-neighbour to vertex i. Let i have d^{+}(i) out-neighbours and d^{−}(i) in-neighbours.

The following graph construction is central to this paper:

Consider a copy of K_{p} with vertices labelled {(1, 1), …, (p, 1)} = {(i, 1) | i ∈ [p]}; call these vertices vertices at level 1, and call this graph D_{1}(K_{p}). Now consider another K_{p} with vertices labelled {(i, 2) | i ∈ [p]}, these are vertices at level 2. For any vertex (i, 2) join it to vertices {(i′, 1) | i⃗i′ ∈ A(D⃗)} at level 1; call this graph D_{2}(K_{p}). 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′ ∈ A(D⃗)} at level 2 and to vertices {(i′, 1) | i⃗i′ ∈ A(D⃗)} at level 1; this is D_{3}(K_{p}).

Now, for any n ≥ 1, consider the graph which has been constructed level by level, up to n levels, according to this definition; call this graph D_{n}(K_{p}) or simply D_{n} when p is clear. We say that the digraph D⃗ generates the sequence {D_{n}} = {D_{1}, D_{2}, …}.

In D_{n} the vertices are of the form (i, j) for every i ∈ [p] and every j, 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′ ∈ A(D⃗).

Call digraph D⃗ uniform if d^{+}(i) = d^{−}(i) for every vertex i in D⃗. Note that D⃗ need not be connected. Then D⃗ is an Eulerian digraph if it has one component, otherwise D⃗ is Eulerian on each of its components.

In this paper we study the sequences {D_{n}}. In Section 2 our main result (Theorem 2.3) states that if D⃗ is uniform then its generated sequence {D_{n}} is K_{p}-removable. In Section 3 we construct sequences in which each graph is regular. We use λ-uniform digraphs; these satisfy λ = d^{+}(i) = d^{−}(i) for every vertex i in D⃗. They can be constructed in a similar manner to Cayley digraphs. We count the exact number of K_{p}’s in the graphs in these sequences. Many examples are given throughout the paper, as well as indications for further research.

2 {D_{n}} is K_{p}-removable for uniform D⃗

In this section we consider {D_{n}}, the sequence of graphs generated by digraph D⃗. Often D⃗ will be uniform. In order to prove that {D_{n}} is K_{p}-removable in this case, we are interested in the K_{p}’s in such D_{n}. The next theorem gives necessary and sufficient conditions for their existence.

For each i ∈ [p], let I_{i} = {(i, 1), …, (i, n)} = {(i, j) | 1 ≤ j ≤ n} be the set of vertices in D_{n} in ‘column i’. Then, because D⃗ is loopless, i.e., i⃗i ∉ A(D⃗), this is an independent set of vertices, the i-th independent set.

Now let V = {(1, v_{1}), …, (p, v_{p})} be an arbitrary vertex subset in D_{n} with exactly one vertex from each independent set I_{i}. Let V have vertices at m different levels: ℓ_{1}, …, ℓ_{m} where ℓ_{1} < ⋯ < ℓ_{m}. For each k, 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} form a level-partition of [p] = {1, …, p}.

Now D_{n}[V] contains the cross-level edge ((i, ℓ_{k}), (i′, ℓ_{k′})) where ℓ_{k′} < ℓ_{k} if and only if i⃗i′ is an arc in D⃗. We call i⃗i′ a V -skew arc. Hence a V -skew arc in D⃗ ‘joins’ different levels of V.

Let \overrightarrow{AB} denote the set of arcs in D⃗ from A to B, i.e., all arcs a⃗b with a ∈ A and b ∈ B.

Theorem 2.1 Let D⃗ be a uniform digraph with p vertices. Then D_{n}[V] is a p-clique in D_{n} if and only if the associated V -skew arcs form a complete symmetric m-partite subdigraph in D⃗.

Proof. Suppose that D_{n}[V] is a p-clique with level-partition V_{1}, …, V_{m}. The digraph D⃗ is uniform so the number of arcs entering any vertex subset equals the number of arcs outgoing from it. Now D_{n}[V] is a p-clique so,

in D⃗, \overrightarrow{V_{k}V_{k′}} is complete for each k′ and k, 1 ≤ k′ < k ≤ m; in particular

\overrightarrow{V_{k}V_{1}} is complete for each k, 2 ≤ k ≤ m. The number of arcs entering V_{1} is

|V_{1}|(|V_{2}| + ⋯ + |V_{m}|) which equals the number of outgoing arcs, hence \overrightarrow{V_{1}V_{k}} is also complete for each k, 2 ≤ k ≤ m.

So \overrightarrow{V_{1}V_{2}} is complete, and we can apply a similar argument to V_{2} to show

that \overrightarrow{V_{2}V_{k}} is complete for each k, 3 ≤ k ≤ m, then to V_{3},..., and so on.

Consequently, \overrightarrow{V_{k′}V_{k}} is complete for each k′ and k, 1 ≤ k′ < k ≤ m, i.e., the V -skew arcs form a complete symmetric m-partite subdigraph in D⃗.

The converse is straightforward.

We usually refer to a p-clique in D_{n} as W. From the construction of D_{n}, for vertex (i, j) in D_{n} its degree is given by

deg(i, j) = d^{+}(i)(j − 1) + d^{−}(i)(n − j) + p − 1.

Corollary 2.2 Let D⃗ be a uniform digraph with p vertices. If D_{n}[W] is a p-clique then the number of edges in D_{n} − W equals the number of edges in D_{n−1}.

Proof. Now D_{n}[W] = K_{p} so the number of edges ‘inside’ W equals the number of edges inside the K_{p} at level n of D_{n}. For any vertex (i, j) in D_{n} we have by uniformity that deg(i, j) = d^{+}(i)(n − 1) + p − 1. So, if (i, j) is in W then its degree ‘outside’ W is d^{+}(i)(n − 1), which is independent of its level j. This outside degree is the same as the degree outside the K_{p} at level n of the level n vertex (i, n). Hence the removal of W from D_{n} removes the same number of edges as the removal of the K_{p} at level n, and so the result.

Now for our main result.

Theorem 2.3 Let D⃗ be a uniform digraph with p vertices. Then its generated sequence of graphs {D_{n}} is K_{p}-removable.

Proof. Suppose W induces a p-clique in D_{n}. Let the vertices of W be {(i, w_{i}) | 1 ≤ i ≤ p}. Now we construct a bijection ϕ between the vertices of D_{n} − W and the vertices of D_{n−1}. Under ϕ, for a fixed i ∈ [p], the vertices in the i-th independent set of D_{n} − W, namely in the set I_{i}\{(i, w_{i})}, are mapped to the vertices in the i-th independent set of D_{n−1}, namely to the set {(i, 1), …, (i, n − 1)}, as follows:

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

Clearly ϕ is a bijection. It is straightforward to show that ϕ moves edges in D_{n} − W to edges in D_{n−1}.

Now, from Corollary 2.2, the graphs D_{n} − W and D_{n−1} have the same number of edges, and so ϕ is an isomorphism. Hence {D_{n}} satisfies P2. Clearly {D_{n}} satisfies P1, which gives the result.

Example 1 p = 3, V (D⃗) = {1, 2, 3}, A(D⃗) = { 12, 21, 23, 32}. Then D⃗ is uniform with 3 vertices. The first three graphs in the K_{3}-removable sequence {D_{n}} are shown in Figure 1 on page 7. Notice the level-partition V_{1} = {1, 3}, V_{2} = {2} which illustrates Theorem 2.1.

6

•  •  • •  •  • •  •  • (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 converse of Theorem 2.3 is not true:

Example 2 p = 3, V (D⃗) = {1, 2, 3}, A(D⃗) = { 12}. Then {D_{n}} is K_{3}- removable, but D⃗ is not uniform.

Question Is every K_{p}-removable sequence isomorphic to the generated sequence of some digraph D⃗? (From Example 2 we know that D⃗ need not be uniform.)

The K_{p}-removable sequence {G_{pn}} is regular if every graph G_{pn} is regular, and irregular otherwise. In general, the sequence {D_{n}} is irregular, see Example 1. It is straightforward to show that all K_{p}-removable sequences with p = 1 or 2 are regular; they will given in Theorem 3.3 below. However, for every p ≥ 3 an irregular K_{p}-removable sequence exists:

Example 3 p ≥ 3, V (D⃗) = [p], A(D⃗) = { 12, 21, 23, 32}. Then D⃗ is uniform with p vertices, so {D_{n}} is K_{p}-removable. However the graph D_{2} is irregular because deg(1, 2) = p but deg(2, 2) = p + 1, so {D_{n}} is irregular.

Call two K_{p}-removable sequences {G_{pn}} and {G′_{pn}} isomorphic, denoted by {G_{pn}} ≅ {G′_{pn}}, if G_{pn} ≅ G′_{pn} for every n ≥ 1.

Let θ : D⃗ → D⃗′ be an isomorphism between uniform digraphs D⃗ and D⃗′. For every fixed n ≥ 1, θ induces an isomorphism Θ between D_{n} and D′_{n} given by: Θ(i, j) = (θ(i), j), for every i ∈ [p] and j with 1 ≤ j ≤ n. Hence, for every n ≥ 1, D_{n} ≅ D′_{n} and so {D_{n}} ≅ {D′_{n}}. We conjecture that the converse is true:

Conjecture Let {D_{n}} and {D′_{n}} be two K_{p}-removable sequences generated by uniform digraphs D⃗ and D⃗′, respectively. If {D_{n}} ≅ {D′_{n}} then D⃗ ≅ D⃗′.

As a final remark we note that the above construction of a K_{p}-removable sequence needs a uniform digraph with vertex set [p]. One way to construct such a uniform digraph is to take an undirected graph H with vertex set [p] and ‘double-orientate’ each edge in H, i.e., replace each edge (i, i′) with two arcs i⃗i′ and i⃗′i. Indeed, D⃗ in Example 1 was obtained from double-orientating the path on 3 vertices.

3 Generating regular (K_{p}, λ)-removable sequences using finite groups

Recall the definition of a regular K_{p}-removable sequence given above.

A uniform digraph D⃗ is called λ-uniform if there is a natural number λ such that λ = d^{+}(i) = d^{−}(i) for every vertex i in D⃗. Note that 0 ≤ λ ≤ p − 1 when D⃗ has p vertices.

We noted in the proof of Corollary 2.2 that, for a uniform digraph D⃗ with p vertices, the degree of any vertex (i, j) in D_{n} is deg(i, j) = d^{+}(i)(n − 1) + p − 1. If D⃗ is λ-uniform, then deg(i, j) = λ(n − 1) + p − 1, which does not depend on i or j. Hence D_{n} is regular of degree λ(n − 1) + p − 1, and {D_{n}} is a regular K_{p}-removable sequence. We call {D_{n}} a regular (K_{p}, λ)-removable sequence.

So, from Theorem 2.3, we have

Theorem 3.1 Let D⃗ be a λ-uniform digraph with p vertices. Then its generated sequence of graphs {D_{n}} is regular (K_{p}, λ)-removable.

In this section we study such regular sequences {D_{n}}. To generate such a sequence we need a λ-uniform digraph. For this we can double-orientate a λ-regular graph H. However, this is only sufficient when such a λ-regular graph exists. Instead, we use a Cayley-type digraph which we obtain from an arbitrary finite group. See Biggs [2] and Grossman and Magnus [4].

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

We form a digraph D⃗ = (\overrightarrow{G_{p}, Λ}) from G_{p} and Λ as follows:

the vertices of D⃗ are {g_{1}, …, g_{p}} and
\overrightarrow{g_{i}g_{i′}} is an arc in D⃗ if and only if g_{i′}g_{i}^{−1} ∈ Λ.

We see that d^{+}(g_{i}) = d^{−}(g_{i}) = |Λ| = λ for every vertex g_{i}, hence D⃗ is λuniform. Consequently, using Theorem 3.1 above, {D_{n}} is a regular (K_{p}, λ)- removable sequence. (Note that Λ need not be a generating set for G_{p}; this

is why we call (\overrightarrow{G_{p}, Λ}) a Cayley-type digraph rather than a Cayley digraph.)

Now for every p ≥ 1 there is a cyclic group with p elements, C_{p}, and a Λ ⊆ C_{p} with e ∉ Λ and |Λ| = λ for each 0 ≤ λ ≤ p − 1; and, permitting henceforth λ = p corresponding to loops in D⃗, for every p ≥ 1 there is a regular (K_{p}, p)-removable sequence, namely {K_{pn}}. So we have the following existence result for regular (K_{p}, λ)-removable sequences:

Theorem 3.2 For every p ≥ 1 and every λ, 0 ≤ λ ≤ p, there exists a regular (K_{p}, λ)-removable sequence.

The cases corresponding to λ = 0, p − 1, and p are especially interesting; they result in sequences that are unique up to isomorphism. Let K_{p×n} = K\underbrace{n, …, n}_{p} be the complete p-partite graph on pn vertices. The proof of the

following Theorem is straightforward.

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

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

and, for every p ≥ 2, (iii) {nK_{p}} is the unique regular (K_{p}, 0)-removable sequence, (iv) {K_{p×n}} is the unique regular (K_{p}, p − 1)-removable sequence,

(v) {K_{pn}} is the unique regular (K_{p}, p)-removable sequence.

The λ-uniform digraphs needed to generate the last three sequences in Theorem 3.3 are: (iii) the 0-uniform digraph with p vertices and no arcs; (iv) the (p−1)-uniform digraph obtained by double-orientating the complete undirected graph K_{p}; and (v) the p-uniform digraph obtained by attaching one loop to each vertex to the digraph in (iv). (Note that in (v) the digraph is not loopless, but the construction still works.)

Example 4 Let ℤ_{p} = {0, 1, …, p − 1} be the additive group (mod p). For λ = 0 set Λ = ∅, and for 1 ≤ λ ≤ p − 1 set Λ = {1, 2, …, λ}, and for λ = p set Λ = ℤ_{p}. Note that in this last case 0 ∈ Λ, contrary to our

previous assumption that e ∉ Λ, but this causes no problems. Then (\overrightarrow{ℤ_{p}, Λ}) generates a regular (K_{p}, λ)-removable sequence for each λ, 0 ≤ λ ≤ p. So

(\overrightarrow{ℤ_{p}, Λ}) generates a spectrum of graph sequences among which are the three sequences of Theorem 3.3(iii)−(v), namely {nK_{p}}, …, {K_{p×n}}, and {K_{pn}}.

As usual let {D_{n}} be the regular (K_{p}, λ)-removable sequence obtained

from a generating digraph D⃗ = (\overrightarrow{G_{p}, Λ}). Analogous to Theorem 2.1, we describe the structure induced on D⃗ from p-cliques in D_{n}.

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 = {(g_{1}, v_{1}), …, (g_{p}, v_{p})} be an arbitrary vertex subset in D_{n} with exactly one vertex from each independent set I_{i} = {(g_{i}, j) | 1 ≤ j ≤ n}. As in Section 2, let V have vertices at m different levels: ℓ_{1}, …, ℓ_{m} where ℓ_{1} < ⋯ < ℓ_{m}. For each k, 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} form a level-partition of G_{p}, and we have:

Theorem 3.4 Let D⃗ = (\overrightarrow{G_{p}, Λ}) be a λ-uniform digraph with generated sequence {D_{n}}. Then D_{n}[V] is a p-clique in D_{n} if and only if each V_{k} is a union of cosets of ⟨\overline{Λ}⟩.

Proof. For any r ≥ 1 let ∏(r) = h_{1} ⋯ h_{r} denote a product of r arbitrary elements h_{1}, …, h_{r} from \overline{Λ}. Clearly for any a ∈ ⟨\overline{Λ}⟩ we can express a as ∏(r) for some fixed r ≥ 1 and some suitably chosen r elements h_{1}, …, h_{r} from \overline{Λ}.

Suppose D_{n}[V] is a p-clique in D_{n} with level partition V_{1}, …, V_{m}. Consider any V_{k} and let g_{i} ∈ V_{k}. Then ∏(1)g_{i} ∈ V_{k} for any ∏(1). For suppose otherwise. Then there exists a ∏(1) = h_{1}, say, with h_{1}g_{i} ∈ V_{k′} for some k′ ≠ k. However, this implies from Theorem 2.1 that \overrightarrow{g_{i}(h_{1}g_{i})} is an arc in D⃗, i.e., (h_{1}g_{i})g_{i}^{−1} = h_{1} ∈ Λ, a contradiction.

Now we show that if any ∏(r)g_{i} ∈ V_{k} then any ∏(r + 1)g_{i} ∈ V_{k}. For suppose that there is a ∏(r +1) = a(r +1) = h_{1} ⋯ h_{r+1} with a(r +1)g_{i} ∉ V_{k}. Then, by similar reasoning to the above, we must have a(r + 1)g_{i} ∈ V_{k′′} for some k′′ ≠ k. Let a(r) = h_{2} ⋯ h_{r+1}; then, by the induction hypothesis, a(r)g_{i} ∈ V_{k}. Hence \overrightarrow{a(r)g_{i}(a(r + 1)g_{i})} is an arc in D⃗, and, as above, h_{1} ∈ Λ, a contradiction.

Hence the induction goes through, and, for any a ∈ ⟨\overline{Λ}⟩ we have ag_{i} ∈ V_{k}, i.e., we have ⟨\overline{Λ}⟩g_{i} ⊆ V_{k}. Hence V_{k} is a union of cosets of ⟨\overline{Λ}⟩.

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

Theorem 3.4 enables us to count the exact number of K_{p}’s in D_{n}. Let |G_{p} : ⟨\overline{Λ}⟩| be the index of ⟨\overline{Λ}⟩ in G_{p}, i.e., the number of cosets of ⟨\overline{Λ}⟩ in G_{p}.

Corollary 3.5 The number of K_{p}’s in D_{n} is 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 D_{n}. 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 D_{n} 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.

Finally we briefly consider three more topics: firstly, we discuss pairs (p, λ) for which there is a unique regular (K_{p}, λ)-removable sequence up to isomorphism; secondly, we prove that if any member of an arbitrary K_{p}- removable sequence {G_{pn}} contains a K_{p+1} then {G_{pn}} = {K_{pn}}; lastly, we list some possibilities for further research.

Let 𝔘 denote the set of pairs (p, λ) for which there is a unique regular (K_{p}, λ)-removable sequence up to isomorphism. Then, from Theorem 3.3, for every p ≥ 1 we have (p, 0), (p, p−1), and (p, p) ∈ 𝔘. Now we use Corollary 3.5 to show that for every even p ≥ 4, we have (p, p − 2) ∉ 𝔘.

Example 5 For every even p ≥ 4 there are at least two non-isomorphic regular (K_{p}, p − 2)-removable sequences:

For the first let G_{p} = D_{\frac{p}{2}} be the dihedral group with p elements, the group of symmetries of the regular \frac{p}{2}-gon. We have D_{\frac{p}{2}} = ⟨a, b | a^{\frac{p}{2}} = b^{2} = (ab)^{2} = e⟩. Let Λ = D_{\frac{p}{2}} \\{e, b\} so that |Λ| = p − 2 and e ∉ Λ. So ⟨\overline{Λ}⟩ = \{e, b\} and |D_{\frac{p}{2}} : ⟨\overline{Λ}⟩| = \frac{p}{2}. Thus D_{n} has n^{\frac{p}{2}} K_{p}’s.

For the second let ℤ_{p} = {0, 1, …, p − 1} be the additive group (mod p). Let Λ = \{1, 2, …, p − 2\}, then |Λ| = p − 2 and 0 ∉ Λ. But p − 1 ∈ \overline{Λ} and p − 1 generates ℤ_{p} i.e., ⟨\overline{Λ}⟩ = ℤ_{p}, and so |ℤ_{p} : ⟨\overline{Λ}⟩| = 1 and D′_{n} has n K_{p}’s.

Thus D_{2} ≅ D̸′_{2} and so {D_{n}} ≅ {D′_{n}}, and for every even p ≥ 4, we have (p, p − 2) ∉ 𝔘. Note that D_{2} is K_{2p} minus the edges of p/2 disjoint 4-cycles, while D′_{2} is K_{2p} minus the edges of a Hamiltonian cycle.

Now we show that if any member of an arbitrary K_{p}-removable sequence {G_{pn}} contains a K_{p+1} then {G_{pn}} = {K_{pn}}.

Theorem 3.6 Suppose that for some n ≥ 2 the n^{th} member, G_{pn}, of the K_{p}-removable sequence {G_{pn}} contains a K_{p+1}. Then G_{pn} = K_{pn} and {G_{pn}} = {K_{pn}}.

Proof. Now G_{pn} contains a K_{p+1}. Since every K_{p} in G_{pn} is part of a partition of V (G_{pn}) into disjoint p-cliques, we may assume without loss of generality that V (G_{pn}) is partitioned into n p-cliques L_{1}, …, L_{n} so that some vertex u in L_{2} is joined to every vertex of L_{1}, i.e., L_{1} ∪ {u} = K_{p+1}. Let v be any vertex in L_{1}. Deleting the n − 1 p-cliques L_{3}, L_{4}, …, L_{n}, L_{1} + {u} − {v} in this order, we obtain the p-clique L_{2} + {v} − {u}. Hence v is adjacent to every vertex of L_{2} and the union of L_{1} and L_{2} is K_{2p}. Consequently, the removal of any n − 2 disjoint K_{p}’s must produce a K_{2p}. This implies that the union of every two levels L_{j} and L_{j′} is K_{2p}; therefore, G_{pn} is a complete graph. Hence G_{pn} = K_{pn}.

Then clearly for every n′ > n we have G_{pn′} = K_{pn′}. And, by removing the required number of K_{p}’s, for every n′ < n we have G_{pn′} = K_{pn′} also. Hence {G_{pn}} = {K_{pn}}.

Some further research possibilities are the following: (A) Investigate the Question and Conjecture mentioned near the end of Section 2. (B) Investigate the set 𝔘; in particular, is (3, 1) ∈ 𝔘?

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].

Acknowledgment The authors thank the referees for providing insight and suggestions that greatly 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.

[4] I. Grossman, W. Magnus, Groups and their Graphs, (Random House, New York, 1964).

[5] D.B. West, Introduction to Graph Theory, 2nd Edition, (Prentice Hall, 2001).