On 02.03.2006 at 12:20 in S5, there is the following noon lecture:
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.
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010