Master of Science (MS)
First Committee Member
Number of Pages
Let n ≥ 2 be a positive integer. For a sequence ( S0, S1, S 2,..Sn-1) of nonnegative integers we study the problem of whether there exists a graph there exists a graph containing i=0n-1Si vertices having exactly Si vertices whose degrees are congruent to i modulo n for each i = 0, 1, 2,.., n-1. When such a graph does exist, the sequence (S0, S 1, S2,..Sn -1) is said to be realizable. It is known for modulo 2, 3, and 4 that such a sequence is realizable with seventeen exceptions for modulo 3 and twenty-four exceptions for modulo 4. These results are known, but concise proofs of these facts have not appeared until this thesis; Further it had been conjectured that for each n ≥ 5 such sequences are realizable with finitely many exceptions. We show that there are finitely many exceptions for modulo 6 and further investigate how our proof technique might be generalized to the modulo 2n case.
Certain; Concerning; Degrees; Existence; Graphs; Problem
University of Nevada, Las Vegas
If you are the rightful copyright holder of this dissertation or thesis and wish to have the full text removed from Digital Scholarship@UNLV, please submit a request to email@example.com and include clear identification of the work, preferably with URL.
Summer, Jonathan Seary, "A problem concerning the existence of graphs with certain degRees" (2005). UNLV Retrospective Theses & Dissertations. 1805.