Balanced Sets in Graphs
Document Type
Article
Publication Date
3-1-2014
Description
Let S ⊆ V be an arbitrary subset of vertices of a graph G = (V,E). The differential ∂(S) of S equals the difference between the number of vertices in V \ S that are adjacent to vertices in S and the number of vertices in S. A nonempty set S is called a balanced set if ∂(S) = 0. In this paper we introduce the study of balanced sets in graphs. Not all graphs have balanced sets, and such graphs are called unbalanced. We give proofs of the existence of balanced sets in various kinds of graphs, such as even order graphs, bipartite graphs, and graphs of maximum degree three. We also investigate unbalanced graphs.
Citation Information
Haynes, Teresa W.; Hedetniemi, Stephen T.; and Scott, Hamilton. 2014. Balanced Sets in Graphs. Utilitas Mathematica. Vol.93 343-356. ISSN: 0315-3681