Very cost effective bipartitions in graphs

For a graph G=(V,E)G=(V,E) and a set of vertices S⊆VS⊆V, a vertex v∈Sv∈S is said to be very cost effective if it is adjacent to more vertices in V∖SV∖S than in SS. A bipartition π={S,V∖S}π={S,V∖S} is called very cost effective if both SS and V∖SV∖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 GG or HH has a very cost effective bipartition, then so does the Cartesian product G□HG□H.