Files in this item
Files  Description  Format 

application/pdf 9411821.pdf (3MB)  (no description provided) 
Description
Title:  Extremal Results and Algorithms for Degree Sequences of Graphs 
Author(s):  Will, Todd Gerald 
Doctoral Committee Chair(s):  West, Douglas B. 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Mathematics 
Abstract:  A 2multigraph is a loopless multigraph with maximum multiplicity 2; pairs of vertices induce 0, 1, or 2 edges. A 2multigraph is parsimonious if it has the minimum number of single edges (multiplicity 1) among all 2multigraphs with the same degree sequence. In every parsimonious 2multigraph, the subgraph of single edges consists of isolated stars and possibly one component that is a triangle. We prove the conjecture of Brualdi and Michael that for any fixed degree sequence, either every parsimonious 2multigraph with those vertex degrees has a triangle of single edges, or no such parsimonious 2multigraph has a triangle of single edges. We determine for a planar graph on n vertices the maximum values for the following: (1) The sum of the m largest vertex degrees. (2) For k $\ge$ 12, the number of vertices of degree at least k and the sum of the degrees of vertices with degree at least k. In addition, for 6 $\le$ k $\le$ 11, we determine upper and lower bounds for the latter two values, which match for certain congruence classes of n. Berge showed that if two graphs G and H have the same degree sequence, then G can be transformed into H by a sequence of elementary degreepreserving transformations. We show that computing the minimum length of such a sequence is an NPcomplete problem. In addition we disprove a conjecture of John Gimbel on an analogous result for oriented graphs, and obtain partial results toward a revised conjecture. 
Issue Date:  1993 
Type:  Text 
Description:  68 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 1993. 
URI:  http://hdl.handle.net/2142/72546 
Other Identifier(s):  (UMI)AAI9411821 
Date Available in IDEALS:  20141217 
Date Deposited:  1993 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois