Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 02.03.2006 at 12:20 in S5, there is the following noon lecture:

Degree matrices

Jose Soto

Abstract

We say that a square matrix M is a degree matrix of a given graph G if there is a (so called) equitable partition of its vertices into blocks B_1,...,B_r such that whenever two vertices belong to the same block, they have the same number of neighbors inside any block:

If u,v belong to B_i then for all j: |N(u) cap B_j|=|N(v) cap B_j|=m_ij

We ask now whether for a given degree matrix M, there exists a graph G such that M is the degree matrix of G, and in addition, for any two edges e,f connecting the same pair of blocks there exists an automorphism of G that

* (1) sends e to f.

* (2) swaps e and f.

For the weaker condition, we fully characterize the matrices for which such a graph exists and show a way to construct one, and for the stronger one we show some progress in their study.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010