$K_p$-Removable Sequences of Graphs

Abstract

Let $\{G_{pn}|n\ge 1\}=\{G_{p1},G_{p2},G_{p3},\dots \}$ 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\ge 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,\lambda )$-removable sequences, where $\lambda \$isafixednumber,\text{(}0\le \lambda \le p$, referring to the fact that $G_{pn}$ is $(\lambda (n–1)+p–1)$-regular. We classify regular $(K_p,0)$-, $(K_p,p–1)$-, and $(K_p,p)$-removable sequences as the sequences $\{n{K}_p|n\ge 1\}$, $\{K_{p\times n}|n\ge 1\}$, and $\{K_{pn}|n\ge 1\}$ respectively. Regular sequences are also constructed using `levelled’ Cayley graphs, based on a finite group. Some examples are given.