1 results
NONREGULAR GRAPHS WITH MINIMAL TOTAL IRREGULARITY
- Part of
-
- Journal:
- Bulletin of the Australian Mathematical Society / Volume 92 / Issue 1 / August 2015
- Published online by Cambridge University Press:
- 29 April 2015, pp. 1-10
- Print publication:
- August 2015
-
- Article
-
- You have access
- Export citation
-
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.
