Friendly and unfriendly k-partitions

Abstract

A friendly partition of a graph is a partition of the vertices into two sets so that every vertex has at least as many neighbors (adjacent vertices) in its own set as in the other set. An unfriendly partition of a graph is a partition of the vertices into two sets so that every vertex has at least as many neighbors in the other set as in its own set. In this paper we extend these concepts to k-partitions of vertices. We define and explore friendly and unfriendly edge partitions and extend these concepts to k-partitions of edges. In extending these concepts to the edges of a graph, we will show that one type of a friendly vertex partition of a K[subscript m,n] graph can be used to produce a friendly edge partition. We will also look at partitions that are both friendly and unfriendly (dual). We will investigate these properties for several types of graphs (star, tree, K[subscript n], C[subscript n], K[subscript m,n]).