ON α,β CYCLE-CONTRACTIBLE GRAPHS

Abstract

A connected, simple graph G of order v is said to be α,β destructible with respect to E′ and V′ if α,β are factors of v and an a-set of edges, E′, exists whose removal from G isolates exactly the vertices in a β-set, V′. In this paper we consider graphs G which are α,β destructible with respect to E′ and V′ such that G-E′-V′ is a cycle of order v-β and call such a graph α,β cycle-contractible with respect to E′ and V′. We characterize graphs of nullity one containing a cycle of order v-β where B|v, consider cycle-stable graphs and characterize destructible graphs (i) reconstructible from a single cycle-remnant, and (ii) whose remnants consist only of cycles or θ.