A CHARACTERIZATION OF STABLE GRAPHS ON A MAXIMUM(MINIMUM) NUMBER OF EDGES

Abstract

A connected, nontrivial, simple graph of order v is said to be α,β destructible if α,β are factors of v and an α-set of edges, E', exists whose removal from G isolates exactly the vertices in α,β-set V'. Graphs which are not α,β destructible for any α,β are called stable, If G is a stable graph on a prime number p ≥ 7 of vertices, then we show that G has a maximum number of edges if and only if G is K_2,p-2, We also characterize stable graphs on a minimum number of edges.