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.

Share

COinS