Philippine E-Journals

Let G = (V,E) be a connected simple graph. A non-empty subset C of V is a separator of G if there exist two non-empty subsets A and B of V such that {A,B,C} is a partition of V , max{|A|, |B|} ≤ ½ |V |, and no edge of G joins a vertex in A and a vertex in B. If G has a separator, its separability sep(G) is the cardinality of a minimum separator of G. This paper characterizes singleton and doubleton separators of graphs. It determines the separabilities of some special graphs, sum of graphs, and graphs resulting from deletion of edges.