Balanced sets in graphs

Abstract

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.