Back to results
University of Illinois at Urbana-Champaign
Extremal Results and Algorithms for Degree Sequences of Graphs
Abstract
dc:descriptionA 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.
Degree
thesis:*- Name thesis:degree_name
- Ph.D.
- Level thesis:degree_level
- Dissertation
- Discipline thesis:degree_discipline
- Mathematics
- Grantor
- University of Illinois at Urbana-Champaign
- Year dc:date
- 2014
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Will, Todd Gerald
- Contributors dc:contributor
-
- West, Douglas B.
Subjects
dc:subject × 1Identifiers
dc:identifier.*- Identifier
- (UMI)AAI9411821
- OAI identifier oai:identifier
- oai:www.ideals.illinois.edu:2142/72546