Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
irregularity; Laplacian matrix; degree; Laplacian index
irregularity; Laplacian matrix; degree; Laplacian index
Summary:
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 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 $.
References:
[1] Abdo, H., Cohen, N., Dimitrov, D.: Bounds and computation of irregularity of a graph. Preprint: http://arxiv.org/abs/1207.4804 (2012).
[2] Albertson, M. O.: The irregularity of a graph. Ars Comb. 46 (1997), 219-225. MR 1470801 | Zbl 0933.05073
[3] Fath-Tabar, G. H.: Old and new Zagreb indices of graphs. MATCH Commun. Math. Comput. Chem. 65 (2011), 79-84. MR 2797217 | Zbl 1265.05146
[4] Fiedler, M.: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czech. Math. J. 25 (1975), 619-633. MR 0387321 | Zbl 0437.15004
[5] Hansen, P., Mélot, H.: Variable neighborhood search for extremal graphs. IX: Bounding the irregularity of a graph. Graphs and Discovery S. Fajtolowicz et al. Proc. DIMACS working group, Piscataway, USA, 2001. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 69, AMS Providence 253-264 (2005). MR 2193452 | Zbl 1095.05019
[6] Henning, M. A., Rautenbach, D.: On the irregularity of bipartite graphs. Discrete Math. 307 (2007), 1467-1472. DOI 10.1016/j.disc.2006.09.038 | MR 2311120 | Zbl 1126.05060
[7] Merris, R.: A note on Laplacian graph eigenvalues. Linear Algebra Appl. 285 (1998), 33-35. MR 1653479 | Zbl 0931.05053
[8] Merris, R.: Laplacian matrices of graphs: A survey. Linear Algebra Appl. 197-198 (1994), 143-176. MR 1275613 | Zbl 0802.05053
[9] Mohar, B.: Some applications of Laplace eigenvalues of graphs. Graph Symmetry: Algebraic Methods and Applications G. Hahn et al. Proc. NATO Adv. Study Inst., Montréal, Canada, 1996. NATO ASI Ser., Ser. C, Math. Phys. Sci. 497, Kluwer Academic Publishers Dordrecht (1997), 225-275. MR 1468791 | Zbl 0883.05096
[10] Zhou, B., Luo, W.: On irregularity of graphs. Ars Comb. 88 (2008), 55-64. MR 2426406 | Zbl 1224.05110
Search
Partner of
