A spectral bound for graph irregularity

作者：Goldberg Felix^*

来源：Czechoslovak Mathematical Journal, 2015, 65(2): 375-379.

DOI：10.1007/s10587-015-0182-5

• irregularity
• Laplacian matrix
• degree
• Laplacian index

The imbalance of an edge e = {u, v} in a graph is defined as i(e) = |d(u)-d(v)|, where d(center dot) is the vertex degree. The irregularity I(G) of G is then defined as the sum of imbalances over all edges of G. This concept was introduced by Albertson who proved that I(G) a (c) 1/2 4n (3)/27 (where n = |V(G)|) and obtained stronger bounds for bipartite and triangle-free graphs. Since then a number of additional bounds were given by various authors. In this paper we prove a new upper bound, which improves a bound found by Zhou and Luo in 2008. Our bound involves the Laplacian spectral radius lambda.

• 出版日期2015-6