A spectral bound for graph irregularity.

DOI10.1007/S10587-015-0182-5MaRDI QIDQ2947995zbMATH OpenOpenAlexFDO

Authors Felix Goldberg

Publication date 29 September 2015

Published in Czechoslovak Mathematical Journal (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.3867, http://hdl.handle.net/10338.dmlcz/144276

zbMATH Keywords

degreeirregularityLaplacian indexLaplacian matrix

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

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)leqfrac{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$.

Recommendations

• Some new spectral bounds for graph irregularity
• Variable neighborhood search for extremal graphs. IX: Bounding the irregularity of a graph
• scientific article; zbMATH DE number 1409213
• A note on spectral radius and maximum degree of irregular graphs
• The spectral radius of irregular graphs

Cites work

• A note on Laplacian graph eigenvalues
• scientific article; zbMATH DE number 5844262 (Why is no real title available?)
• scientific article; zbMATH DE number 3681933 (Why is no real title available?)
• scientific article; zbMATH DE number 1054729 (Why is no real title available?)
• scientific article; zbMATH DE number 1409213 (Why is no real title available?)
• Laplacian matrices of graphs: A survey
• Old and new Zagreb indices of graphs
• On the irregularity of bipartite graphs
• Variable neighborhood search for extremal graphs. IX: Bounding the irregularity of a graph

Cited in

(11)

• The Moore bound for irregular graphs
• Lower bounds on the irregularity of trees and unicyclic graphs
• On the irregularity of \(\pi \)-permutation graphs, Fibonacci cubes, and trees
• Some new spectral bounds for graph irregularity
• scientific article; zbMATH DE number 5844262 (Why is no real title available?)
• Molecular trees with the sixth, seventh and eighth minimal irregularity values
• Variable neighborhood search for extremal graphs. IX: Bounding the irregularity of a graph
• The extremal irregularity of connected graphs with given number of pendant vertices
• New results on imbalance graphic graphs
• The reciprocal irregularity of a graph
• On the minimum reformulated Albertson Index of fixed-order trees and unicyclic graphs with a given maximum degree

This page was built for publication: A spectral bound for graph irregularity.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947995)