A spectral bound for graph irregularity

Felix Goldberg

Czechoslovak Mathematical Journal (2015)

  • Volume: 65, Issue: 2, page 375-379
  • ISSN: 0011-4642

Abstract

top
The imbalance of an edge e = { u , v } in a graph is defined as i ( e ) = | d ( u ) - d ( v ) | , where d ( · ) 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 ) ≤ 4 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 2008. Our bound involves the Laplacian spectral radius λ .

How to cite

top

Goldberg, Felix. "A spectral bound for graph irregularity." Czechoslovak Mathematical Journal 65.2 (2015): 375-379. <http://eudml.org/doc/270098>.

@article{Goldberg2015,
abstract = {The imbalance of an edge $e=\lbrace u,v\rbrace $ 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) \le 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 $.},
author = {Goldberg, Felix},
journal = {Czechoslovak Mathematical Journal},
keywords = {irregularity; Laplacian matrix; degree; Laplacian index; irregularity; Laplacian matrix; degree; Laplacian index},
language = {eng},
number = {2},
pages = {375-379},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {A spectral bound for graph irregularity},
url = {http://eudml.org/doc/270098},
volume = {65},
year = {2015},
}

TY - JOUR
AU - Goldberg, Felix
TI - A spectral bound for graph irregularity
JO - Czechoslovak Mathematical Journal
PY - 2015
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 65
IS - 2
SP - 375
EP - 379
AB - The imbalance of an edge $e=\lbrace u,v\rbrace $ 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) \le 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 $.
LA - eng
KW - irregularity; Laplacian matrix; degree; Laplacian index; irregularity; Laplacian matrix; degree; Laplacian index
UR - http://eudml.org/doc/270098
ER -

References

top
  1. Abdo, H., Cohen, N., Dimitrov, D., Bounds and computation of irregularity of a graph, Preprint: http://arxiv.org/abs/1207.4804 (2012). (2012) 
  2. Albertson, M. O., The irregularity of a graph, Ars Comb. 46 (1997), 219-225. (1997) Zbl0933.05073MR1470801
  3. Fath-Tabar, G. H., Old and new Zagreb indices of graphs, MATCH Commun. Math. Comput. Chem. 65 (2011), 79-84. (2011) Zbl1265.05146MR2797217
  4. Fiedler, M., A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czech. Math. J. 25 (1975), 619-633. (1975) Zbl0437.15004MR0387321
  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). (2005) Zbl1095.05019MR2193452
  6. Henning, M. A., Rautenbach, D., 10.1016/j.disc.2006.09.038, Discrete Math. 307 (2007), 1467-1472. (2007) Zbl1126.05060MR2311120DOI10.1016/j.disc.2006.09.038
  7. Merris, R., A note on Laplacian graph eigenvalues, Linear Algebra Appl. 285 (1998), 33-35. (1998) Zbl0931.05053MR1653479
  8. Merris, R., Laplacian matrices of graphs: A survey, Linear Algebra Appl. 197-198 (1994), 143-176. (1994) Zbl0802.05053MR1275613
  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. (1997) Zbl0883.05096MR1468791
  10. Zhou, B., Luo, W., On irregularity of graphs, Ars Comb. 88 (2008), 55-64. (2008) Zbl1224.05110MR2426406

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.