IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

28th Cumberland Conference on Combinatorics, Graph Theory & Computing

Kayvan Sadeghi
Carnegie Mellon University

On the maximum number of non-zeros in graphical joint degree matrices

  • Authors: Éva Czabarka, J. Rauh, Kayvan Sadeghi, Taylor Short, & László Székely
  • May 16, 2015
  • 10 a.m.
  • Gambrell 151

Graphical joint degree matrices (JDMs) are n-1 by n-1 matrices whose (i,j) element represents the number of edges between vertices of degree i and vertices of degree j in a graph with n nodes. Finding the maximum possible number of non-zero elements of a graphical JDM for a fixed number of nodes seems quite challenging. In this talk, we discuss and motivate this problem based on statistical random graph analysis. We provide reasonable lower and upper bounds for this maximum number as well as a conjecture for the asymptotic maximum number of non-zero elements of a graphical JDM and graphs that attain it.

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