Very cost effective bipartitions in graphs
Teresa W. Haynes, Stephen T. Hedetniemi, Inna Vasylieva · AKCE International Journal of Graphs and Combinatorics · 2015
For a graph and a set of vertices , a vertex is said to be very cost effective if it is adjacent to more vertices in than in . A bipartition is called very cost effective if both and 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 or has a very cost effective bipartition, then so does the Cartesian product .