Noon lecture
list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)
On 2.3.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 | 2018 | 2019 | 2020 | newer lectures)
Webmaster: kamweb.mff.cuni.cz Archive page