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.
Recommended Citation
McSorley, John P. and Porter, Thomas D. "K_p-Removable Sequences of Graphs." Journal of Combinatorial Mathematics and Combinatorial Computing 45 (Jan 2003): 43-62.