Comments

Published in Discrete Mathematics, 287(1-3), 85-91.

Abstract

Let {Gp1,Gp2, . . .} be an infinite sequence of graphs with Gpn having pn vertices. This sequence is called Kp-removable if Gp1Kp, and GpnSGp(n−1) for every n ≥ 2 and every vertex subset S of Gpn that induces a Kp. Each graph in such a sequence has a high degree of symmetry: every way of removing the vertices of any fixed number of disjoint Kp’s yields the same subgraph. Here we construct such sequences using componentwise Eulerian digraphs as generators. The case in which each Gpn is regular is also studied, where Cayley digraphs based on a finite group are used.