Back to search

East Tennessee State University

Bipartitions Based on Degree Constraints

Abstract

dc:description.abstract

For a graph G = (V,E), we consider a bipartition {V1,V2} of the vertex set V by placing constraints on the vertices as follows. For every vertex v in Vi, we place a constraint on the number of neighbors v has in Vi and a constraint on the number of neighbors it has in V3-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.

Degree

thesis:*
Name thesis:degree_name
MS (Master of Science)
Level thesis:degree_level
Thesis - unrestricted
Discipline thesis:degree_discipline
Mathematical Sciences
Year dc:date.issued
2014

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Delgado, Pamela I

Subjects

dc:subject × 5

Rights

dc:rights
Statement dc:rights
  • Copyright by the authors.

Identifiers

dc:identifier.*
Repository record dc:identifier
https://dc.etsu.edu/etd/2410

Chain of custody

source
Harvested from
East Tennessee State University
Base URL
dc.etsu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Delgado, Pamela I. Bipartitions Based on Degree Constraints. Thesis - unrestricted thesis, 2014. https://dc.etsu.edu/etd/2410