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.