Article ID Journal Published Year Pages File Type
4654819 European Journal of Combinatorics 2008 13 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,