期刊名称：AKCE International Journal of Graphs and Combinatorics
印刷版ISSN：0972-8600
出版年度：2015
卷号：12
期号：2-3
页码：155-160
DOI：10.1016/j.akcej.2015.11.009
语种：English
出版社：Elsevier
摘要：AbstractFor a graphG=(V,E)and a set of verticesS⊆V, a vertexv∈Sis said to be very cost effective if it is adjacent to more vertices inV∖Sthan inS. A bipartitionπ={S,V∖S}is called very cost effective if bothSandV∖Sare 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 graphGorHhas a very cost effective bipartition, then so does the Cartesian productG□H.
