Bipartitions Based on Degree Constraints

Author

Pamela I. Delgado, East Tennessee State UniversityFollow

Degree Name

MS (Master of Science)

Program

Mathematical Sciences

Date of Award

8-2014

Committee Chair or Co-Chairs

Teresa Haynes

Committee Members

Robert Gardner, Debra Knisley

Abstract

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 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.

Document Type

Thesis - unrestricted

Recommended Citation

Delgado, Pamela I., "Bipartitions Based on Degree Constraints" (2014). Electronic Theses and Dissertations. Paper 2410. https://dc.etsu.edu/etd/2410

Copyright

Copyright by the authors.