Nonregular graphs with minimal total irregularity

DOI10.1017/S0004972715000271MaRDI QIDQ5501742zbMATH OpenOpenAlexFDO

Authors Hosam Abdo, Darko Dimitrov

Publication date 14 August 2015

Published in Bulletin of the Australian Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

extremal graphstotal irregularity

Mathematics Subject Classification ID

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

Abstract: The {it total irregularity} of a simple undirected graph $G$ is defined as ${mirr}_t(G)=$ $frac12su{m}_{u,vinV(G)}$ $left|d_G(u)-d_G(v)ight|$, where $d_G(u)$ denotes the degree of a vertex $uinV(G)$. Obviously, ${mirr}_t(G)=0$ if and only if $G$ is regular. Here, we characterize the non-regular graphs with minimal total irregularity and thereby resolve the recent conjecture by Zhu, You and Yang~cite{zyy-mtig-2014} about the lower bound on the minimal total irregularity of non-regular connected graphs. We show that the conjectured lower bound of $2n-4$ is attained only if non-regular connected graphs of even order are considered, while the sharp lower bound of $n-1$ is attained by graphs of odd order. We also characterize the non-regular graphs with the second and the third smallest total irregularity.

Recommendations

• The minimal total irregularity of some classes of graphs
• Note on non-regular graphs with minimal total irregularity
• scientific article; zbMATH DE number 7020668
• The total irregularity of a graph
• The maximal total irregularity of some connected graphs

Cites work

• A note on a theorem of Erdős and Gallai
• A note on the irregularity of graphs
• Graphs with maximal irregularity
• Highly irregular graphs
• How to Define an Irregular Graph
• On the irregularity of bipartite graphs
• Spektren endlicher Grafen

Cited in

(14)

• On the \(\sigma_t\)-irregularity and the inverse irregularity problem
• scientific article; zbMATH DE number 7020668 (Why is no real title available?)
• Bounds and optimal results for the total irregularity measure
• Minimum Total Irregularity Index Of The Tricyclic Graphs
• Relations between total irregularity and non-self-centrality of graphs
• Maximum non-self-centrality number of trees with a fixed number of pendant vertices
• Ordering of \(c\)-cyclic graphs with respect to total irregularity
• Note on irregular graphs
• Graphs with maximal \(\sigma\) irregularity
• Note on non-regular graphs with minimal total irregularity
• Graph irregularity and its measures
• The minimal total irregularity of some classes of graphs
• A smallest irregular oriented graph containing a given diregular one
• Comparison between the non-self-centrality number and the total irregularity of graphs

This page was built for publication: Nonregular graphs with minimal total irregularity

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