Files in this item
|(no description provided)|
|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|
|Degree Granting Institution:||University of Illinois at Urbana-Champaign|
|Abstract:||A 2-multigraph is a loopless multigraph with maximum multiplicity 2; pairs of vertices induce 0, 1, or 2 edges. A 2-multigraph is parsimonious if it has the minimum number of single edges (multiplicity 1) among all 2-multigraphs with the same degree sequence. In every parsimonious 2-multigraph, 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 2-multigraph with those vertex degrees has a triangle of single edges, or no such parsimonious 2-multigraph 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 degree-preserving transformations. We show that computing the minimum length of such a sequence is an NP-complete 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.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1993.
|Date Available in IDEALS:||2014-12-17|