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
Recommended Citation
Vasylieva, Inna, "Very Cost Effective Partitions in Graphs" (2013). Electronic Theses and Dissertations. Paper 1137. https://dc.etsu.edu/etd/1137
Copyright
Copyright by the authors.