/^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 9 (2015) 45-50
Comparing the irregularity and the total irregularity of graphs
Darko Dimitrov
Institut für Informatik, Freie Universität Berlin, 14195 Berlin, Germany
Riste Skrekovski *
Department of Mathematics, University of Ljubljana, 1000 Ljubljana and Faculty of Information Studies, 8000 Novo Mesto, Slovenia
Received 9 June 2012, accepted 15 August 2013, published online 13 June 2014
Abstract
Albertson [4] has defined the irregularity of a simple undirected graph G as irr(G) = J2uvee(g) |dG(u) - dG(v)|, where dG(u) denotes the degree of a vertex u G V(G). Recently, in [1] a new measure of irregularity of a graph, so-called the total irregularity, was defined as irrt(G) = 2J2u v£V(G) |dG(u) - dG(v)|. Here, we compare the irregularity and the total irregularity of graphs. For a connected graph G with n vertices, we show that irrt(G) < n2irr(G)/4. Moreover, if G is a tree, then irrt(G) < (n — 2)irr(G).
Keywords: The irregularity of graph, the total irregularity of graph. Math. Subj. Class.: 05C05, 05C07,05C99
1 Introduction
Let G be a simple undirected graph of order n = |V(G)| and size m = |E(G)|. For v G V(G), the degree of v, denoted by dG(v), is the number of edges incident to v. Albert-son [4] defines the imbalance of an edge e = uv G E(G) asimbG(uv) = |dG(u) - dG(v)| and the irregularity of G as
irr(G) = ^ imbG(uv).	(1.1)
uveE(G)
Obviously, a connected graph G has irregularity zero if and only if G is regular. In [4] Albertson presented upper bounds on irregularity for bipartite graphs, triangle-free graphs
* Partially supported by Slovenian ARRS Program P1-00383 and Creative Core - FISNM - 3330-13-500033. E-mail addresses: dimdar@zedat.fu-berlin.de (Darko Dimitrov), skrekovski@gmail.com (Riste Skrekovski)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
45
Ars Math. Contemp. 9 (2015) 93-107
and arbitrary graphs, as well as a sharp upper bound for trees. Some results about the irregularity of bipartite graphs are given in [4, 14]. Related to the work of Albertson is the work of Hansen and Melot [13], who characterized the graphs with n vertices and m edges with maximal irregularity. Various upper bounds on the irregularity of a graph were given in [19], where Kr+1-free graphs, trees and unicyclic graphs with fixed number of vertices of degree one were considered. In [16], relations between the irregularity and the matching number of trees and unicyclic graphs were investigated. More results on irregularity, imbalance and related measures, one can find in [3, 5, 6, 17, 18].
Recently, in [1] a new measure of irregularity of a simple undirected graph, so-called the total irregularity, was defined as
irrt(G) = 2 £ |dG(u) - dG(v)|.	(1.2)
u,veV (G)
Other approaches, that characterize how irregular a graph is, have been proposed [2, 3, 7, 8, 9, 10, 15]. In this paper, we focus on the relation between the irregularity (1.1) and the total irregularity (1.2) of a graph.
In the sequel we introduce the notation used in the rest of the paper. For u, v E V(G), we denote by dG(u, v) the length of a shortest path in G between u and v. In this short paper the notation of the sets, that will be defined next, is always regarding the graph G we consider. By Va,b, we denote a set of vertices of a graph with degrees in [a, b], and by V>a (resp. V<a), we denote a set of vertices of a graph with degrees at least a (resp. with degrees at most a). Similarly, by V>a (resp. V<a), we denote a set of neighboring vertices of a vertex x with degrees at least a (resp. with degrees at most a). The corresponding cardinalities of the above mentioned sets, we denote by small v (e.g., v<a = |V<a | or vXa = |V|a|).
A subgraph T = v1v2 • • • v; of a graph G, where v; is a leaf in G, is called a tread if dG(v1) = dG(v2) = • • • = dG(v;-1) = 2, and v1 is adjacent to a vertex with degree at least three. Let T = v1v2 • • • vs and T2 = u1u2 • • • u; be two threads of a graph G with leaves vs and u;, respectively, and let v0 be the other neighbour of v1. By G' = G(T2 o T\) we denote a graph that is obtained from G after a concatenation of T2 to T\, i.e., after deleting the edge v0v1 and adding an edge between u; and v1.
2 General graphs
Obviously, irr(G) < irrt(G). And, it is not hard to show that equality holds precisely when all non-adjacent vertices have same degree. Such a class of graphs are the complete k-partite graphs. More examples of graphs with equal irregularity and total irregularity can be found in [11]. Now, we give an upper bound on irrt(G) in term of irr(G).
Theorem 2.1. Let G be a connected graph on n-vertices. Then
2
n2
irrt(G) < — irr(G). Moreover, the bound is sharp for infinitely many graphs.
Proof. Let T be a spanning tree of G. Then, any two vertices a, b of G are connected by an unique path Pab = x1x2 • • • xs in T, where x1 = a and xs = b. By the triangle inequality,
D. Dimitrov and R. Skrekovski: Comparing the irregularity and the total irregularity of graphs 47
we have that
G) =
irrt(G) = 1 £ |dG(a) - dG(b)|	(2.1)
a,beV (G)
2
- 1 £ |^g(Xi) - dG(x2)| + |dG(x2) - dG(xs)| +
a,b£V (G)
For an edge uv G E(T), let nu = {x | x G V(T) and dT(x,u) < dT(x,v)}. Similarly, let nv = {x | x G V(T) and dT(x, u) > dT(x, v)}. Each summand |dG(u) — dG(v)| in the last sum of (2.1) occurs in the sum exactly nuv = nunv times. Also, each summand |dG(v) - dG(u)| occurs nuv times. Thus,
irrt(G) < £ |dG(u) - dG(v)|nuv.
uv£E(T)
As nuv < (n/2)(n/2) = n74, and Euv£E(T) |dG(u) - dG(v)| < EuveE(G) |dG(u) -
dG (v) |, we obtain the desired inequality.
Now, we show that the bound n2/4 is sharp. Let a, b be two distinct integers, say a < b. Consider a graph Ga whose all vertices are of degree a, with exception of one vertex u which is of degree a - 1. Similarly, consider a graph Gb whose all vertices are of degree b, with exception of one vertex u which is of degree b - 1. Let G* be the graph obtained from Ga and Gb by connecting u and v. Let na = |V(Ga)| and nb = |V(Gb)|. Observe that irr(G*) = b - a and irrt(G*) = (b - a)nanb. Choosing na = nb = n/2, we obtain
irrt(G*)	n2
■	= nanb = -¡-.
irr(G*)	4
In order to show that such graphs Ga and Gb exist, one may use the theorem of Erdos-Gallai [12] which states that a sequence di > d2 > • • • > dn of non-negative integers with even sum is graphic (i.e., there exist a graph with such a degree sequence) if and only if
r	n
^dj < r(r - 1) + min(r, dj),	(2.2)
i=1	j=r+1
for all 1 < r < n.
So, fix a, b, and na = nb to be odd numbers with na > max{a, b}. We will show the existence of the graph Ga. In a similar way, one can show the existence of the graph Gb. As (na - 1)a + (a - 1) is even, the parity condition of the theorem of Erdos-Gallai is satisfied. So, we need to show only (2.2). For this we consider three cases regarding r and a:
•	r < a - 1. Then, (2.2) can be written as ra < r(r - 1) + (na - r)r. It obviously holds since a C na - r.
•	r = a. In this case, (2.2) can be written as ra < r(r - 1) + (na - r)r - 1, which holds for a similar reason as the previous case.
•	r > a + 1. Similarly, (2.2) can be written as ra < r(r - 1) + (na - r)a - 1, and it
holds as ra C r(r - 1).
□
48
Ars Math. Contemp. 9 (2015) 93-107
3 Trees
In this section, we give an upper bound on irrt(G) in term of irr(G), when G is a tree. To show the bound, we will use the following lemma.
Lemma 3.1. Let G be a tree, x a vertex of degree d > 3 incident with threads T and T2, and let G' = G(T2 o Ti). Then,
(a)	irrt(G) - irrt(G') = 2v2,d_i;
(b)	irr(G) - irr(G') = 2(d - v>d - 1).
Proof. Let T = aia2 • • • as and T2 = 6i62 • • • 6;. We consider the identities separately.
(a)	Notice that all other vertices except x and 6, have the same degree in G and G'. Hence, it holds that
irrt(G) - irrt(G') = ^ (|dG(x) - dG(u)| - |dG/(x) - dG/ (u)|)
+ ^(|dG (u) - dG(b; )| - |dG' (u) - dG' (6, )|)
+ |dG(x) - dG(6,)| - |dG'(x) - dG'(6,)|. Since dG' (x) = dG(x) - 1 = d - 1 and dG' (6;) = dG(6,) + 1 = 2, further we have irrt(G) - irrt(G') = ^ (|d - dG(u)| - |d - 1 - dG(u)|)
u=bj
+ ^(|dG(u) - 1|-|dG(u) - 2|) + 2. (3.1)
If u € V<d_i, then |d - dG(u)| - |d - 1 - dG(u)| = 1, otherwise |d - dG(u)| -|d - 1 - dG(u)| = -1. Hence, the first sum in (3.1) is equal to v<d-i - 1 - v>d. Similarly, if u € V>2, then |dG(u) - 1| - |dG(u) - 2| = 1, otherwise |dG(u) - 1| -|dG(u) - 2| = -1. Thus, the second sum in (3.1) is equal to v>2 - 1 - vi. Applying these observations, we have
irrt(G) - irrt(G') = v<d_i - 1 - v>d + v>2 - 1 - vi +2 = v<d_i - vi + v>2 - v>d = 2v2,d_i.
(b)	Let ei = xai, e2 = xbi, e3 = 6;_i6; and Ei = {ei, e2, e3}. Denote by E2 the set of edges incident to x that are different from ei and e2. Notice that every edge not in Ei U E2 contributes zero to the difference irr(G) - irr(G'). So, we can infer
irr(G) - irr(G') = ^^ (imbG(uv) - imbG' (uv))
+ ^ (imbG(uv) - imbG'(uv)).
uvGEi
D. Dimitrov and R. Skrekovski: Comparing the irregularity and the total irregularity of graphs 49
Notice that the first sum is equal to -v|d + (v:|d-1 - 2) (we have -2 as the edges e1 and e2 are excluded in this sum). In G', the edge e1 = xa1 does not exist anymore, but there is a new edge ei = bla1. Observe that after the concatenation T2 o T1 all other edges preserve their end-vertices. First, we consider the contribution of e1 and e1 in irr(G) - irr(G'). There are two possibilities regarding the length of T1:
•	s = 1: Then, imbG(e1) = d - 1 andimbc (e1) = 1;
•	s > 2: In this case, imbG(e1) = d - 2 and imbG (e1) = 0.
In both of them, we obtain imbG(e1) - imbG' (e1) = d - 2.
Next, we consider the contributions of e2 and e3 together. Again, consider two possibilities regarding the length of T2:
•	l = 1: Then, e2 = e3 and imbG(e2) = d - 1 and imbG'(e2) = d - 3;
•	l > 2: In this case, e2 = e3, and imbG(e2) = d - 2, imbG(e2) = d - 3, imbG(e3) = 1 andimbG (e3) = 0.
In both cases, we obtain that J2ee{e2 e3}(imbG(e) - imbG'(e)) = 2. So finally, we have that
irr(G) - irr(G') = -v|d + (v|d-1 - 2) + d - 2 + 2
= -v>d + vXd-1 - 2 + d = 2(d - vXd - 1).
□
Theorem 3.1. Let G be a tree with n vertices. Then
irrt(G) < (n - 2)irr(G). Moroever, equality holds if and only if G is a path.
Proof. Let n1 (G) be the number of vertices of G with degree one. We will prove the second inequality by induction on n1(G). If n1(G) = 0, then G ~ P1, irr(G) = irrt(G) = 0, and the equality in the theorem holds. Since G is a tree, n1 (G) = 1. If n1(G) = 2, then G ~ Pn. In this case irr(G) = 2 and irrt(G) = 2(n - 2), hence we obtain equality.
Now, assume n1 (G) > 2. Then, it is easy to see that G has a vertex x of degree d > 3, incident with at least two threads T\ and T2. Let G' = G(T2 o T\). Since n1(G') = n1(G) - 1, we can assume that inequality holds for G', i.e.,
irrt(G') < (n - 2)irr(G').	(3.2)
By Lemma 3.1, we have
irr(G') = irr(G) - 2(d - v|d - 1) and irrt(G') = irrt(G) - 2v2,d-1. (3.3) Plugging (3.3) in (3.2), we obtain
(n - 2)irr(G) > irrt(G) - 2v2,d-1 + 2(n - 2)(d - v|d - 1). (3.4)
As d(x) = d > 3 and x is incident with two threads, we infer v|d + 2 < d, and so
2(d - v|d - 1) > 2. Observe also that v2,d-1 < n - 3. Hence 2(n-2)(d - vxd - 1) > 2(n - 3) > 2v2,d-1. This together with (3.4) gives (n - 2)irr(G) > irrt(G).	□
50
Ars Math. Contemp. 9 (2015) 115-124
References
[1]	H. Abdo, S. Brandt and D. Dimitrov, The total irregularity of a graph, Discrete Math. Theor. Comput. Sci. 16 (2014), 201-206.
[2]	Y. Alavi, A. Boals, G. Chartrand, P. Erdos and O. R. Oellermann, k-path irregular graphs, Congr. Numer. 65 (1988) 201-210.
[3]	Y. Alavi, G. Chartrand, F. R. K. Chung, P. Erdos, R. L. Graham and O. R. Oellermann, Highly irregular graphs, J. Graph Theory 11 (1987) 235-249.
[4]	M. O. Albertson, The irregularity of a graph, Ars Comb. 46 (1997) 219-225.
[5]	F. K. Bell, A note on the irregularity of graphs, Linear Algebra Appl. 161 (1992) 45-54.
[6]	Y. Caro and R. Yuster, Graphs with large variance, Ars Comb. 57 (2000) 151-162.
[7]	G. Chartrand, P. Erdos and O. R. Oellermann, How to define an irregular graph, Coll. Math. J. 19 (1988) 36-42.
[8]	G. Chartrand, K. S. Holbert, O. R. Oellermann and H. C. Swart, F-degrees in graphs, Ars Comb. 24 (1987) 133-148.
[9]	L. Collatz and U. Sinogowitz, Spektren endlicher Graphen, Abh. Math. Sem. Univ. Hamburg
21	(1957) 63-77.
[10]	D. Cvetkovic and P. Rowlinson, On connected graphs with maximal index, Publications de l'Institut Mathematique (Beograd) 44 (1988) 29-34.
[11]	D. Dimitrov, T. Reti, Graphs with equal irregularity indices, Acta Polytech. Hung. 11 (2014), 41-57.
[12]	P. Erdos and T. Gallai, Graphs with prescribed degrees of vertices, (in Hungarian) Mat. Lapok. 11 (1960) 264-274.
[13]	P. Hansen and H. Melot, Variable neighborhood search for extremal graphs 9. Bounding the irregularity of a graph, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 69 (1962) 253-264.
[14]	M. A. Henning and D. Rautenbach, On the irregularity of bipartite graphs, Discrete Math. 307 (2007) 1467-1472.
[15]	D. E. Jackson and R. Entringer, Totally segregated graphs, Congress. Numer. 55 (1986) 159165.
[16]	W. Luo and B. Zhou, On the irregularity of trees and unicyclic graphs with given matching number, Util. Math. 83 (2010) 141-147.
[17]	D. Rautenbach and I. Schiermeyer, Extremal problems for imbalanced edges, Graphs Comb.
22	(2006) 103-111.
[18]	D. Rautenbach and L. Volkmann, How local irregularity gets global in a graph, J. Graph Theory 41 (2002) 18-23.
[19]	B. Zhou and W. Luo, On irregularity of graphs, Ars Combin. 88 (2008) 55-64.