Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4654819 | European Journal of Combinatorics | 2008 | 13 Pages |
We say that a square matrix M of order rr is a degree matrix of a given graph GG if there is a so-called equitable partition of its vertices into rr blocks with the following property: For any ii and jj it holds that a vertex from the iith block of the partition has exactly mi,jmi,j neighbors inside the jjth block.We ask whether for a given degree matrix M, there exists a graph GG such that M is a degree matrix of GG, and in addition, for any two edges e,fe,f spanning between the same pair of blocks there exists an automorphism of GG that sends ee to ff. In this work we affirmatively answer the question for all degree matrices and show a way to construct a graph that witnesses this fact.We further explore a case where the automorphism is required to exchange a given pair of edges and show some positive and negative results.