Files in this item



application/pdf9411821.pdf (3MB)Restricted to U of Illinois
(no description provided)PDF


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.
Issue Date:1993
Description:68 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1993.
Other Identifier(s):(UMI)AAI9411821
Date Available in IDEALS:2014-12-17
Date Deposited:1993

This item appears in the following Collection(s)

Item Statistics