Degree Sequence Variants of Some Classical Problems

A non-negative integer sequence π is the degree sequence of a simple graph G. In this case, we say that G π or is a realization of π. As a given graphic sequence may have a number of nonisomorphic realizations, a great deal of research has focused on determining when a given graphic sequence has a realization with a given property. Along these lines, this talk will give a broad introduction to some areas of research that can be viewed as degree sequence variants of several widely studied problem in the graph theory literature.

Two n-vertex graphs G-1 and G-2 pack if they can be expressed as edge-disjoint subgraphs of the complete graph on n vertices. Here we will introduce a degree sequence analogue to graph packing, give some new results and discuss applications to discrete imaging science. We will also cover some questions related to the problem of determining when a graphic sequence has realization containing a specific subgraph. These include a new degree sequence variant of graph Ramsey numbers, and a degree sequence variant of the Turfan problem.

Event Topic

Networks and Optimization