Geodesic
A spectral bound for graph irregularity
Czechoslovak Mathematical Journal, Tome 65 (2015) no. 2, pp. 375-379 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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 $.
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 $.
DOI : 10.1007/s10587-015-0182-5
Classification : 05C07, 05C35, 05C50
Keywords: irregularity; Laplacian matrix; degree; Laplacian index 
@article{10_1007_s10587_015_0182_5,
     author = {Goldberg, Felix},
     title = {A spectral bound for graph irregularity},
     journal = {Czechoslovak Mathematical Journal},
     pages = {375--379},
     year = {2015},
     volume = {65},
     number = {2},
     doi = {10.1007/s10587-015-0182-5},
     mrnumber = {3360433},
     zbl = {06486953},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0182-5/}
}
TY  - JOUR
AU  - Goldberg, Felix
TI  - A spectral bound for graph irregularity
JO  - Czechoslovak Mathematical Journal
PY  - 2015
SP  - 375
EP  - 379
VL  - 65
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0182-5/
DO  - 10.1007/s10587-015-0182-5
LA  - en
ID  - 10_1007_s10587_015_0182_5
ER  - 
%0 Journal Article
%A Goldberg, Felix
%T A spectral bound for graph irregularity
%J Czechoslovak Mathematical Journal
%D 2015
%P 375-379
%V 65
%N 2
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0182-5/
%R 10.1007/s10587-015-0182-5
%G en
%F 10_1007_s10587_015_0182_5
Goldberg, Felix. A spectral bound for graph irregularity. Czechoslovak Mathematical Journal, Tome 65 (2015) no. 2, pp. 375-379. doi: 10.1007/s10587-015-0182-5

[1] Abdo, H., Cohen, N., Dimitrov, D.: Bounds and computation of irregularity of a graph. Preprint: (2012). | arXiv

[2] Albertson, M. O.: The irregularity of a graph. Ars Comb. 46 (1997), 219-225. | MR | Zbl

[3] Fath-Tabar, G. H.: Old and new Zagreb indices of graphs. MATCH Commun. Math. Comput. Chem. 65 (2011), 79-84. | MR | Zbl

[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 | Zbl

[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 | Zbl

[6] Henning, M. A., Rautenbach, D.: On the irregularity of bipartite graphs. Discrete Math. 307 (2007), 1467-1472. | DOI | MR | Zbl

[7] Merris, R.: A note on Laplacian graph eigenvalues. Linear Algebra Appl. 285 (1998), 33-35. | MR | Zbl

[8] Merris, R.: Laplacian matrices of graphs: A survey. Linear Algebra Appl. 197-198 (1994), 143-176. | MR | Zbl

[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 | Zbl

[10] Zhou, B., Luo, W.: On irregularity of graphs. Ars Comb. 88 (2008), 55-64. | MR | Zbl

Cité par Sources :