A spectral bound for graph irregularity

Czechoslovak Mathematical Journal

Felix ¹ 

[1] Caesarea-Rothschild Institute, University of Haifa, Mount Carmel, Haifa 31905, Israel

关键词: irregularity;    Laplacian matrix;    degree;    Laplacian index;   

DOI  :  

学科分类：数学（综合）

来源: Akademie Ved Ceske Republiky

【 摘 要 】

The imbalance of an edge $e=\{u,v\}$ in a graph is defined as $i(e)=|d(u)-d(v)|$, where $d(\cdot)$ 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) \leq4n^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$.

【 授权许可】

Unknown