## Files in this item

FilesDescriptionFormat

application/pdf

9411821.pdf (3MB)
(no description provided)PDF

## 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 Urbana-Champaign Degree: Ph.D. Genre: Dissertation Subject(s): Mathematics 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 Type: Text Description: 68 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1993. URI: http://hdl.handle.net/2142/72546 Other Identifier(s): (UMI)AAI9411821 Date Available in IDEALS: 2014-12-17 Date Deposited: 1993
﻿