IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

An extremal problem related to degree sequences of graphs

  • Nov. 14, 2014
  • 2:30 p.m.
  • LeConte 312


Let $G$ be a simple graph without isolated vertices and with degree sequence $d _ 1 \ge d _ 2 \ge \cdots \ge d _ n$. The joint degree matrix (JDM) of $G$ is an $(n-1)$ by $(n-1)$ matrix where the $ij$-th position has the number of edges that connect vertices of degree $i$ to vertices of degree $j$. We consider the following problem: asymptotically, what's the maximum number of non-zero entries of a JDM? We will present our best known bounds and discuss room for improvement.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster