Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-17T04:25:49.511Z Has data issue: false hasContentIssue false

NONREGULAR GRAPHS WITH MINIMAL TOTAL IRREGULARITY

Part of:Graph theory

Published online by Cambridge University Press:  29 April 2015

HOSAM ABDO
Affiliation:
Department of Mathematics and Computer Science, Freie Universität Berlin, Takustraße 9, D-14195 Berlin, Germany email abdo@mi.fu-berlin.de
DARKO DIMITROV*
Affiliation:
Department of Engineering Sciences I, Hochschule für Technik und Wirtschaft Berlin, Wilhelminenhofstraße 75A, D-12459 Berlin, Germany email darko.dimitrov11@gmail.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The total irregularity of a simple undirected graph $G$ is defined as $\text{irr}_{t}(G)=\frac{1}{2}\sum _{u,v\in V(G)}|d_{G}(u)-d_{G}(v)|$, where $d_{G}(u)$ denotes the degree of a vertex $u\in V(G)$. Obviously, $\text{irr}_{t}(G)=0$ if and only if $G$ is regular. Here, we characterise the nonregular graphs with minimal total irregularity and thereby resolve the recent conjecture by Zhu et al. [‘The minimal total irregularity of graphs’, Preprint, 2014, arXiv:1404.0931v1 ] about the lower bound on the minimal total irregularity of nonregular connected graphs. We show that the conjectured lower bound of $2n-4$ is attained only if nonregular connected graphs of even order are considered, while the sharp lower bound of $n-1$ is attained by graphs of odd order. We also characterise the nonregular graphs with the second and the third smallest total irregularity.

MSC classification

Information

Type
Research Article
Copyright
© 2015 Australian Mathematical Publishing Association Inc.