Physical Sciences and Mathematics Commons^™

Bipartitions Based On Degree Constraints, Pamela I. Delgado

Electronic Theses and Dissertations

For a graph G = (V,E), we consider a bipartition {V₁,V₂} 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 …