A NOTE ON GRAPHS WHOSE DESTRUCTIONS YIELD COMPLETE SUBGRAPHS

Abstract

A connected graph G of order p =|V| and sise q =| E | is said to be (a_i, b_i)-destructible (with respect to E_i and V_i say) if a_i,b_i are integral factors of p and an a_i-set of edges E_i exists whose removal from G results in exactly b_i components isomorphic to K_i i.e. whose removal from G isolates the vertices in a b_i-set V_i. The operation of removing E_i and V_i from G results in either Ø or a subgraph H of G and is called an (a_i , b_i)-destruction of G. In this paper we show that the only graphs whose every (a_i,b_i)- destruction results in a complete subgraph are K (1,2) and K₄—e, where e ε K₄.