pith. sign in

arxiv: 1308.3867 · v1 · pith:QFCEUGE7new · submitted 2013-08-18 · 🧮 math.CO

A spectral bound for graph irregularity

classification 🧮 math.CO
keywords boundboundsdefinedgraphirregularityspectralthenadditional
0
0 comments X
read the original abstract

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) \leq \frac{n^{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 2011. Our bound involves the Laplacian spectral radius $\lambda$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.