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.