Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4652819 | Electronic Notes in Discrete Mathematics | 2007 | 6 Pages |
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