Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4598996 | Linear Algebra and its Applications | 2015 | 15 Pages |
Abstract
Given a simple graph G , the vertex partition Π: V(G)=V1∪V2∪⋯∪VrV(G)=V1∪V2∪⋯∪Vr is said to be an equitable partition if, for any u∈Viu∈Vi, |Vj∩NG(u)|=bij|Vj∩NG(u)|=bij is a constant whenever 1≤i,j≤r1≤i,j≤r. An equitable partition Π leads to a divisor G/ΠG/Π of G , which is the directed multigraph with vertices V1,V2,…,VrV1,V2,…,Vr and bijbij arcs from ViVi to VjVj. Conversely, a directed multigraph may not be a divisor of some simple graph. In this paper we give a necessary and sufficient condition for a directed multigraph to be the divisor of some simple graph. By the way, we give a method to construct many classes of connected graphs with exactly k main eigenvalues for any positive integer k.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
Authors
Xueyi Huang, Qiongxiang Huang, Lu Lu,