Irregularity of graphs respecting degree bounds

DOI10.37236/11948MaRDI QIDQ6197322zbMATH OpenFDO

Authors Dieter Rautenbach, Florian Werner

Publication date 16 February 2024

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2303.12632

zbMATH Keywords

irregularityvertex degree

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35)

Abstract: Albertson defined the irregularity of a graph $G$ as $irr(G)=sumlimit{s}_{uvinE(G)}|d_G(u)-d_G(v)|$. For a graph $G$ with $n$ vertices, $m$ edges, maximum degree $Delta$, and $d=leftlfloorfracDeltamDeltan-mightfloor$, we show ${\displaystyle }$irr(G)leq d(d+1)n+frac{1}{Delta}left(Delta^2-(2d+1)Delta-d^2-d ight)m.${\displaystyle }$

Review text

Summary: \textit{M. O. Albertson} [Ars Comb. 46, 219--225 (1997; Zbl 0933.05073)] defined the irregularity of a graph \(G\) as \[\operatorname{irr}(G)=\sum\limits_{uv\in E(G)}|d_G(u)-d_G(v)|.\] For a graph \(G\) with \(n\) vertices, \(m\) edges, maximum degree \(\Delta \), and \(d=\left\lfloor \frac{\Delta m}{\Delta n-m}\right\rfloor \), we show \[\operatorname{irr}(G)\leq d(d+1)n+\frac{1}{\Delta}\left(\Delta^2-(2d+1)\Delta-d^2-d\right)m.\]

Recommendations

• Graphs with maximal irregularity
• scientific article; zbMATH DE number 1409213
• Extremely irregular graphs
• Variable neighborhood search for extremal graphs. IX: Bounding the irregularity of a graph
• On maximally irregular graphs

Cites work

• Bounding the Mostar index
• Graphs with maximal irregularity
• Graphs with maximum irregularity
• scientific article; zbMATH DE number 5844262 (Why is no real title available?)
• scientific article; zbMATH DE number 1409213 (Why is no real title available?)
• Maximizing the Mostar index for bipartite graphs and split graphs
• Mostar index: results and perspectives
• On the difference of Mostar index and irregularity of graphs
• On the irregularity of bipartite graphs
• Peripherality in networks: theory and applications
• The extremal irregularity of connected graphs with given number of pendant vertices
• Variable neighborhood search for extremal graphs. IX: Bounding the irregularity of a graph

Cited in

(1)

• The reciprocal irregularity of a graph

This page was built for publication: Irregularity of graphs respecting degree bounds

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