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.

This document is currently not available here.

Share

COinS