Very Cost Effective Bipartitions in Graphs
Document Type
Article
Publication Date
11-1-2015
Description
For a graph G=(V, E) and a set of vertices S⊆ V, a vertex v∈S is said to be very cost effective if it is adjacent to more vertices in V{set minus}. S than in S. A bipartition π= {S, V{set minus}. S} is called very cost effective if both S and V{set minus}. 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 characterize the cactus graphs having a very cost effective bipartition. Also, we show that if a graph G or H has a very cost effective bipartition, then so does the Cartesian product G□ H.
Citation Information
Haynes, Teresa W.; Hedetniemi, Stephen T.; and Vasylieva, Inna. 2015. Very Cost Effective Bipartitions in Graphs. AKCE International Journal of Graphs and Combinatorics. Vol.12(2-3). 155-160. https://doi.org/10.1016/j.akcej.2015.11.009 ISSN: 0972-8600