×

Bipartitions based on degree constraints. (English) Zbl 1312.05104

Summary: For a graph \(G = (V,E)\), we consider a bipartition \(\{V_1,V_2\}\) of the vertex set \(V\) by placing constraints on the vertices as follows. For every vertex \(v\) in \(V_i\), we place a constraint on the number of neighbors \(v\) has in \(V_i\) and a constraint on the number of neighbors it has in \(V_{3-i}\). Using three values, namely 0 (no neighbors are allowed), 1 (at least one neighbor is required), and \(X\) (any number of neighbors are allowed) for each of the four constraints, results in 27 distinct types of bipartitions. The goal is to characterize graphs having each of these 27 types. We give characterizations for 21 out of the 27. Three other characterizations appear in the literature. The remaining three prove to be quite difficult. For these, we develop properties and give characterization of special families.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)