Integral circulant graphs of prime power order with maximal energy

详细信息    查看全文

• 作者：J.W. Sander^a ; ^{sander@imai.uni-hildesheim.de"" rel=""nofollow} ; T. Sander^b ; ^{t.sander@ostfalia.de"" rel=""nofollow}
• 关键词：Cayley graphs ; Integral graphs ; Circulant graphs ; gcd graphs ; Graph energy ; Convex optimization
• 刊名：Linear Algebra and its Applications
• 出版年：2011
• 出版时间：15 December 2011
• 年：2011
• 卷：435
• 期：12
• 页码：3212-3232
• 全文大小：321 K

文摘

The energy of a graph is the sum of the moduli of the eigenvalues of its adjacency matrix. We study the energy of integral circulant graphs, also called gcd graphs, which can be characterized by their vertex count n and a set of divisors of n in such a way that they have vertex set and edge set . Using tools from convex optimization, we analyze the maximal energy among all integral circulant graphs of prime power order p^s and varying divisor sets . Our main result states that this maximal energy approximately lies between s(p-1)p^s-1 and twice this value. We construct suitable divisor sets for which the energy lies in this interval. We also characterize hyperenergetic integral circulant graphs of prime power order and exhibit an interesting topological property of their divisor sets.