Degree Name

MS (Master of Science)

Program

Mathematical Sciences

Date of Award

5-2013

Committee Chair or Co-Chairs

Teresa Haynes

Committee Members

Robert Beeler, Anant Godbole

Abstract

For a graph G=(V,E) and a set of vertices S, a vertex v in S is said to be very cost effective if it is adjacent to more vertices in V -S than in S.

A bipartition pi={S, V- S} is called very cost effective if both S and V- S are very cost effective sets. Not all graphs have a very cost effective bipartition, for example, the complete graphs of odd order do not. We consider several families of graphs G, including Cartesian products and cacti graphs, to determine whether G has a very cost effective bipartition.

Document Type

Thesis - unrestricted

Copyright

Copyright by the authors.

Share

COinS