Article ID Journal Published Year Pages File Type
4652819 Electronic Notes in Discrete Mathematics 2007 6 Pages PDF
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 r blocks such that whenever two vertices belong to the same block, they have the same number of neighbors inside any block.We ask now whether for a given degree matrix M, there exists a graph G such that M is a degree matrix of G, and in addition, for any two edges e, f spanning between the same pair of blocks there exists an automorphism of G that sends e to f. In this work, we fully characterize the matrices for which such a graph exists and show a way to construct one.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics