# A study on total irregularities of certain graphs and digraphs

Johan Kok, Sudev Naduvath

► To cite this version:

Johan Kok, Sudev Naduvath. A study on total irregularities of certain graphs and digraphs. Cogent Mathematics & Statistics, 2016, 3 (1), 10.1080/23311835.2016.1179708. [hal-02263315](https://hal.science/hal-02263315)

HAL Id: hal-02263315

https://hal.science/hal-02263315

Submitted on 4 Aug 2019

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

CrossMark

<figure><img src="image_3.png" /></figure>

Received: 19 October 2015

Accepted: 13 April 2016

*Corresponding author: Naduvath Sudev, Department of Mathematics, Vidya Academy of Science & Technology, Thalakkottukara, Thrissur 680501, India

E-mail: sudevnk@gmail.com

Reviewing editor:
Lishan Liu, Qufu Normal University,
China

Additional information is available at
the end of the article

## PURE MATHEMATICS | RESEARCH ARTICLE

# A study on total irregularities of certain graphs and digraphs

Johan Kok¹ and Naduvath Sudev²*

**Abstract:** The total irregularity of a simple undirected graph G is denoted by *irr*<sub>*t*</sub>(*G*) and is defined as *irr*<sub>*t*</sub>(*G*) = <sup>1</sup>&frasl;<sub>2</sub> &sum;<sub>u,v&isin;V(*G*)</sub> |d(*u*) - d(*v*)|. In this paper, we introduce the notion of edge-transformation in relation to total irregularity of simple graphs with at least one cut edge as well as an edge-joint between two graphs. We also introduce the notion of total irregularity with respect to in-degree and out-degree in directed graphs. We also introduce the concept of total irregularity in respect of in-degree and out-degree in simple directed graphs. These invariants are called total in-irregularity and total out-irregularity, respectively. In this paper, we initiate a study on these parameters of given simple undirected graphs and simple digraphs.

**Subjects:** Advanced Mathematics; Combinatorics; Discrete Mathematics; Mathematics & Statistics; Science

**Keywords:** total irregularity; branch-transformation; edge-transformation; edge-joint; total in-irregularity; total out-irregularity

**Mathematics Subject classifications:** 05C07; 05C20; 05C38; 05C75

### 1. Introduction

For general notations and concepts in graph theory, we refer to Bondy and Murty (1976), Harary (1969), West (2001) and for digraph theory, we further refer to Chartrand and Lesniak (2000), Jensen

## ABOUT THE AUTHORS

Johan Kok is registered with the South African Council for Natural Scientific Professions (South Africa) as a professional scientists in both Physical Science and Mathematical Science. His main research areas are in Graph Theory and the reconstruction of motor vehicle collisions. He has been endorsed by international peers as skilled in a wide range of combinatorica disciplines. Johan has a keen interest in mathematics education as well.

Naduvath Sudev has been working as a professor (Associate) in the Department of Mathematics, Vidya Academy of Science and Technology, Thrissur, India, for the last 15 years. His primary research areas are Graph Theory and Combinatorics. He is a reviewer of Mathematical Reviews and Zentralblatt MATH and reviewer of more than 15 journals. He has more than 40 publications in different international journals.

## PUBLIC INTEREST STATEMENT

Major real world applications of irregularities of graphs are in chemical graph theory, biological and economical systems. Results stemming from operations between graphs or structurally changing a graph, are enhanced through this study related to branch-transformation and the introduction of an edge joint. The immediate application of edge-joint is to gain an understanding of stringing of graphs and many biological structures can be modelled as graphs stringed sequentially. With regards to directed graphs the field of study is wide open. Directed graphs allow the analysis of the influence a vertex (the tail) has over a neighbour (the head). Applications lies in the initial modelling of directed graphs as null-graphs with vertices carrying floating out-arcs seeking heads. A vertex with zero floating out-arcs can only be a head of one or more vertices, hence resembles a black hole in cosmic space. Modelling cosmic systems as null-graphs with vertices carrying floating out-arcs seeking heads is regarded as a promising new application.
and Gutin (2007). All graphs mentioned in this paper are simple, connected and finite graphs, unless mentioned otherwise. Also, except for Section 4, all the graphs mentioned here are undirected graphs.

A graph G is said to be regular if the degree of all vertices are equal. A graph that is not regular is called an irregular graph. The total irregularity of a given simple connected graph is defined in Albertson (1997) as follows.

**Definition 1.1** (Albertson, 1997) The imbalance of an edge e = uv in a given graph G is defined as |d(u) - d(v)|. The total irregularity of a graph G, denoted by *irr*<sub>*t*</sub>(G), is defined as

$$
irr_t(G) = \frac{1}{2} \sum_{u,v \in V(G)} |d(u) - d(v)|.
$$

If the vertices of a graph G on n vertices are labelled as v<sub>i</sub>, i = 1, 2, 3, ..., n, then the definition
may be irr<sub>t</sub>(G) = 1/2 &sum;<sub>i=1</sub><sup>n</sup> &sum;<sub>j=1</sub><sup>n</sup> |d(v<sub>i</sub>) - d(v<sub>j</sub>)| = &sum;<sub>i=1</sub><sup>n</sup> &sum;<sub>j=1</sub><sup>n</sup> |d(v<sub>i</sub>) - d(v<sub>j</sub>)| or &sum;<sub>i=1</sub><sup>n-1</sup> &sum;<sub>j=i+1</sub><sup>n</sup> |d(v<sub>i</sub>) - d(v<sub>j</sub>)|. For a
graph on a singular vertex (1-null graph or K<sub>1</sub>), we define irr<sub>t</sub>(G) = 0. Clearly, irr<sub>t</sub>(G) = 0 if and only if
G is regular.

If an edge e is a cut-edge of the graph G and a component of G − e is a tree T, then T is called a
hanging tree of G. The notion of branch-transformation of a graph has been introduced in Zhu, You,
and Yang (in press) as follows.

**Definition 1.2** (Zhu et al., in press) Let G be a graph with at least two pendant vertices. Without loss of generality, let u be a vertex of G with $d_G(u) \ge 3$, T be a hanging tree of G connecting to u with $|V(T)| \ge 1$ and v be a pendant vertex of G with v $\notin$ T. Let G' be the graph obtained from G by deleting T from vertex u and attaching it to vertex v. We call the transformation from G to G' a branch-transformation on G from vertex u to vertex v.

Certain studies on irregularities and total irregularities of given graphs and the properties of graphs related to these irregularities have been done in Abdo, Brandt, and Dimitrov (2014), Abdo, Cohen, and Dimitrov (in press), Abdo and Dimitrov (2014), Albertson (1997), Dimitrov and Škrekovski (2015), Henning and Rautenbach (2007), Zhu et al. (in press). There are many specific results in respect of cut vertices and cut-edges in the studies on various concepts in graph theory. Many applications rely on either the existence of cut-vertices or cut edges as well. Where stringing of graphs is required through linking graphs pairwise through adding a single edges between pairs of vertices, multiple cut-edges exist in the resultant stringed graph. The order of stringing may, in some instances, not obey the commutative property with respect to certain invariants. For directed graphs, orientated stringing is generally more complex and may require extremal graph theoretic analysis.

Motivated from these observations, in this paper, we introduce the notion of edge-transformation
in relation to total irregularity of simple graphs with at least one cut edge as well as an edge-joint
between two graphs. We also introduce the notion of total irregularity with respect to in-degree and
out-degree in directed graphs and initiate a study on certain types of total irregularities of given
classes of directed and undirected graphs.

## 2. Total irregularity resulting from edge-joints

Consider a graph G on n vertices with two connected components $G_1$ and $G_2$. Therefore, $G = G_1 \cup G_2$.
Hence, the total irregularity of G is given by $irr_t(G) = irr_t(G_1) + irr_t(G_2) + \sum_{i=1}^r \sum_{j=1}^s |d(u_i) - d(v_j)|$, where
$u_i \in V(G_1)$, $v_j \in V(G_2)$ and $r = |V(G_1)|$ and $s = |V(G_2)|$.

The concept of an edge-joint between two simple undirected graphs G and H is defined below.
**Definition 2.1** The edge-joint of two graphs G and H is the graph obtained by adding one edge, say uv, where u ∈ V(G), v ∈ V(H), and is denoted by G ~ uv H.

**Remark 2.2** It is to be noted that G ~ uv H = G ∪ H + uv and G ~ uv H ≅ H ~ vu G.

Let G be a graph on n vertices with two connected components G₁ and G₂ whose vertex sets are V(G₁) = {u₁: 1 ≤ i ≤ r} and V(G₂) = {vᵢ: 1 ≤ j ≤ s}. We fix the vertices u₁ from G₁ and v₁ from G₂. Now, we define the vertex subsets V₁ = {uₓ:dG₁(uₓ) ≤ dG₁(u₁), x ≠ 1}; V₂ = {uᵧ:dG₁(uᵧ) > dG₁(u₁)} and let |V₁| = a and |V₂| = b. Then, choose V₃ = {vₓ:dG₂(vₓ) ≤ dG₁(u₁)} and V₄ = {vᵧ:dG₂(vᵧ) > dG₁(u₁)}, where |V₃| = a* and |V₄| = b*. Similarly, let V₅ = {vz:dG₂(vz) ≤ dG₂(v₁), z ≠ 1} and V₆ = {vw:dG₂(vw) > dG₂(v₁)} where |V₅| = c and |V₆| = d and choose V₇ = {uz:dG₁(uz) ≤ dG₂(v₁)} and V₈ = {uw:dG₁(uw) > dG₂(v₁)} where |V₇| = c* and |V₈| = d*.

Define the variables b = r - a, d = s - c = n - r - c, b* = r - a* and d* = s - c* = n - r - c*.

**THEOREM 2.3** Let G be a graph on n vertices with two connected components G₁ and G₂, where V(G₁) = {u₁: 1 ≤ i ≤ r} and V(G₂) = {vᵢ: 1 ≤ j ≤ s}. Let G' = G₁ ~ uv₁v₁ G₂. Then, we

have
$$
\operatorname{irr}_t(G') = \operatorname{irr}_t(G_1) + \operatorname{irr}_t(G_2) + \sum_{i=1}^{r} \sum_{j=1}^{s} |d_{G_1}(u_i) - d_{G_2}(v_j)| + 2n - 2(b + b^* + d + d^*) - 2
$$
or
$$
\operatorname{irr}_t(G') = \operatorname{irr}_t(G_1) + \operatorname{irr}_t(G_2) + \sum_{i=1}^{r} \sum_{j=1}^{s} |d_{G_1}(u_i) - d_{G_2}(v_j)| + 2(a + a^* + c + c^*) - 2n + 2.
$$

Proof Clearly, for the graph G = G₁ ∪ G₂, we have $irr_t(G) = irr_t(G_1) + irr_t(G_2) + \sum_{i=1}^{r} \sum_{j=1}^{s} |d_{G_1}(u_i) - d_{G_2}(v_j)|$ with $|V(G_1)| = r$ and $|V(G_2)| = s$.

By increasing $d_{G_1}(u_1)$ by 1 we increase the partial sum $\sum_{j=1}^{a} |d_{G_1}(u_1) - d_{G_1}(w_j)|$ by exactly $(a-1)$. It also reduces the partial sum $\sum_{j=1}^{b} |d_{G_1}(u_1) - d_{G_1}(w_j)|$ by exactly b. It also increases the partial sum $\sum_{j=1}^{a'} |d_{G_1}(u_1) - d_{G_2}(w_j)|$ by exactly a* and decreases the partial sum $\sum_{j=1}^{b'} |d_{G_1}(u_1) - d_{G_2}(w_j)|$ by exactly b*. Furthermore, by increasing $d_{G_2}(v_1)$ by 1, we increase $w_j \in V_4$ the partial sum $\sum_{j=1}^{c} |d_{G_2}(v_1) - d_{G_2}(w_j)|$ by exactly (c-1). It also reduces the partial sum $\sum_{j=1}^{d} |d_{G_1}(u_1) - d_{G_2}(w_j)|$ by exactly d. It also increases the partial sum $\sum_{j=1}^{c'} |d_{G_1}(u_1) - d_{G_1}(w_j)|$ by exactly c* and decreases the partial sum $\sum_{j=1}^{d'} |d_{G_1}(u_1) - d_{G_1}(w_j)|$ by exactly d*. Hence, we have an interim result as follows.
$$w_j \in V_8$$

$$
\begin{align*}
\operatorname{irr}_t(G') &= \operatorname{irr}_t(G_1) + \operatorname{irr}_t(G_2) + \sum_{i=1}^{r} \sum_{j=1}^{s} |d_{G_1}(u_i) - d_{G_2}(v_j)| + (a-1)b + a^*-b^* + (c-1)d + c^*-d^* \\
&= \operatorname{irr}_t(G_1) + \operatorname{irr}_t(G_2) + \sum_{i=1}^{r} \sum_{j=1}^{s} |d_{G_1}(u_i) - d_{G_2}(v_j)| + (a-b)(a^*-b^*) + (c-d)(c^*-d^*) - 2.
\end{align*}
$$

By substituting the variables b, d, b* and d* as defined in Definition the final result is as follows.

$$
\operatorname{irr}_t(G') = \operatorname{irr}_t(G_1) + \operatorname{irr}_t(G_2) + \sum_{i=1}^{r} \sum_{j=1}^{s} |d_{G_1}(u_i) - d_{G_2}(v_j)| + 2n - 2(b + b^* + d + d^*) - 2, \quad \text{or;}
$$
$$irr_t(G') = irr_t(G_1) + irr_t(G_2) + \sum_{i=1}^{r} \sum_{j=1}^{s} |d_{G_1}(u_i) - d_{G_2}(v_j)| + 2(a + a^* + c + c^*) - 2n + 2, \text{ follows.} \quad \square$$

Clearly $irr_t(G')$ is edge dependent in general but we have the following Corollary.

**COROLLARY 2.4** Let the degree sequence of graphs $G_1$ and $G_2$ be $(d_{G_1}(u_1) \le d_{G_1}(u_2) \le d_{G_1}(u_3) \le \dots \le d_{G_1}(u_n))$ and $(d_{G_2}(v_1) \le d_{G_2}(v_2) \le d_{G_2}(v_3) \le \dots \le d_{G_2}(v_m))$, respectively. If $d_{G_1}(u_i) = d_{G_2}(v_j)$ for some $i, j$ and $d_{G_1}(u_k) = d_{G_2}(v_l)$ for some $k, l$ and $G' = G_1 \rightsquigarrow_{u_i v_j} G_2$ then, $irr_t(G') = irr_t(G'')$.

**Proof** Begin the proof by choosing any vertex degree value $t_1$ in the degree sequence of $G_1$ and identify largest vertex index say, $i$ for which $d_{G_1}(u_i) = t_1$. Similarly, choose any vertex degree value $t_2$ in the degree sequence of $G_2$ and identify largest vertex index say, $l$ for which $d_{G_2}(v_l) = t_2$. Here, we have to consider the following cases.

**Case-1:** With respect to $G' = G_1 \rightsquigarrow_{u_i v_j} G_2$, set the values as follows.

(i) $|V_1| = a = i - 1,$

(ii) $|V_2| = b = n - i,$

(iii) $|V_3| = a^* = j,$

(iv) $|V_4| = b^* = m - j,$

(v) $|V_5| = c = l - 1,$

(vi) $|V_6| = d = m - l,$

(vii) $|V_7| = c^* = k,$

(viii) $|V_8| = d^* = n - k.$

Therefore, we have

$$2(n + m) - 2((n - i) + (m - j) + (m - l) + (n - k)) - 2 = 2(i + j + k + l - (n + m)) - 2.$$

**Case-2:** In respect of $G'' = G_1 \rightsquigarrow_{u_k v_j} G_2$, set the values as follows.

(i) $|V_1| = a = k - 1,$

(ii) $|V_2| = b = n - k,$

(iii) $|V_3| = a^* = l,$

(iv) $|V_4| = b^* = m - l,$

(v) $|V_5| = c = j - 1,$

(vi) $|V_6| = d = m - j,$

(vii) $|V_7| = c^* = i,$

(viii) $|V_8| = d^* = n - i.$

Therefore, here we have
$$2(n + m) - 2((n - k) + (m - l) + (m - j) + (n - i)) - 2 = 2(k + l + j + i - (n + m)) - 2.$$

Since Case-1 and Case-2 yield the same result, the result $irr_t(G') = irr_t(G'')$ follows from Theorem 2.3. $\square$

An immediate consequence of Corollary 2.4 is that for regular graphs $G_1$ and $G_2$ we have $irr_t(G_1 \rightsquigarrow_{v_u v_2} G_2)$ $u \in V(G_1) \lor v \in V(G_2)$ is a constant. This result is proved in the following proposition.
**Proposition 2.5** For the regular graphs $G_1, G_2$ on $n, m$ vertices, respectively, with $d_{G_1}(u) \ge d_{G_2}(v)$ we have

$$ \mathrm{irr}_t(G_1 \rightsquigarrow_{uv} G_2) = \begin{cases} 2(n+m)-2, & \text{if } d_{G_1}(u) = d_{G_2}(v), \\ n m | d_{G_1}(u) - d_{G_2}(v)| + 2(n-1), & \text{if } d_{G_1}(u) > d_{G_2}(v). \end{cases} $$

*Proof* The proof follows immediately from Corollary 2.4. □

We note that if $G_1$ and $G_2$ are of equal $k$-regularity, then $\mathrm{irr}_t(G_1 \rightsquigarrow_{uv} G_2)$ is independent of the $k$-degree of the vertices.

**3. Total irregularity due to edge-transformation**

Consider a graph $G$ on $n = l_1 + l_2$ vertices and a cut edge $u_1v_1$. Let $G = (G_1 \cup G_2) + u_1v_1$, $u_1 \in V(G_1) = \{u_i: 1 \le i \le l_1\}$ and $v_1 \in V(G_2) = \{v_j: 1 \le j \le l_2\}$. Edge-transformation with respect to $u_1$ will be the graph $G^{u_1v_1}$ obtained by deleting the edge $u_1v_1$ and adding the edge $u_1v_1$ for any $i \ne 1$. We call $G_1$ the master graph and $G_2$ the slave graph.

Let us now introduce the notion of edge-transformation partitioning of a vertex set of a given graph as follows.

**Definition 3.1** The edge-transformation partitioning of the vertex set $V(G)$ of a graph $G$ on $n$ vertices with at least one cut edge say $u_1v_1$, is defined to be $V_h = \{u_i, v_k: d_{G_1}(u_i) = d_{G_1}(u_1) - 1$ and $d_{G_2}(v_k) = d_{G_1}(u_1) - 1\} \cup \{u_1\}$, $h = |V_h|$, and $V_s = \{u_i, v_k: d_{G_1}(u_i) > d_{G_1}(u_1) - 1$ and $d_{G_2}(v_k) > d_{G_1}(u_1) - 1\}$, $s = |V_s|$, and $V_t = \{u_i, v_k: d_{G_1}(u_i) < d_{G_1}(u_1) - 1$ and $d_{G_2}(v_k) < d_{G_1}(u_1) - 1\}$, $t = |V_t|$.

Invoking Definition 3.1, we now define certain vertex sets in $G$ as given below. Let $V_s = \{u_j, v_k: d_{G_1}(u_j) \le d_{G_1}(u_i) \text{ and } d_{G_2}(v_k) \le d_{G_2}(u_i) \text{ and } u_j, v_k \in V_s\}$, $m = |V_{s_1}|$, and $V_{s_2} = \{u_j, v_k: d_{G_1}(u_j) > d_{G_1}(u_i) \text{ and } d_{G_2}(v_k) > d_{G_2}(u_i) \text{ and } u_j, v_k \in V_s\}$, $l = |V_{s_2}|$, and $V_{t_1} = \{u_j, v_k: d_{G_1}(u_j) \le d(u_i) \text{ and } d_{G_2}(v_k) \le d_{G_2}(u_i) \text{ and } u_j, v_k \in V_t\}$, $m_1 = |V_{t_1}|$, and $V_{t_2} = \{u_j, v_k: d_{G_1}(u_j) > d_{G_1}(u_i) \text{ and } d_{G_2}(v_k) > d_{G_2}(u_i) \text{ and } u_j, v_k \in V_t\}$, $l_1 = |V_{t_2}|$.

In view of the above notions, we propose the following theorem.

**THEOREM 3.2** For a graph $G$ with a cut edge $u_1v_1$, let $G - u_1v_1 = G_1 \cup G_2$. After edge-transformation in respect of $v_1$ we have

$$ \mathrm{irr}_t(G^{u_1v_1}) = \begin{cases} \mathrm{irr}_t(G), & \text{if } d_{G_1}(u_i) = d_{G_1}(u_1) - 1, \\ \mathrm{irr}_t(G) + 2m, & \text{if } d_{G_1}(u_i) > d_{G_1}(u_1) - 1, \\ \mathrm{irr}_t(G) - 2(h + l_1), & \text{if } d_{G_1}(u_i) < d_{G_1}(u_1) - 1. \end{cases} $$

*Proof* If $d_{G_1}(u_i) = d_{G_1}(u_1) - 1$, then reducing $d_{G_1}(u_1)$ by 1, reduces the partial sum $\sum^h_j = 1 |d_{G_1}(u_1) - d(w_j)|$ by exactly $(h-1)$. It increases the partial sum $\sum^s_j = 1 |d_{G_1}(u_1) - d(w_j)|$ by exactly $s$ and finally it reduces the the partial sum $\sum^t_j = 1 |d_{G_1}(u_1) - d(w_j)|$ by exactly $t$. $w_j \in V_t$

**Case 1:** By increasing $d_{G_1}(u_i), u_i \in V_h$ by 1, the partial sum $\sum^h_j = 1 |d_{G_1}(u_1) - d(w_j)|$ increases by exactly $(h-1)$. It decreases the partial sum $\sum^s_j = 1 |d_{G_1}(u_1) - d(w_j)|$ by exactly $s$ and $w_j \in V_s$
finally it increases the the partial sum $\sum_{j=1}^{n} |d_{G_i}(u_j) - d(w_j)|$ by exactly $t$. Hence, the result, $w_j \in V_t$
$$ \text{irr}_t(G^{u,v_1}) = \text{irr}_t(G) - (h-1) + s - t + ((h-1) - s + t) = \text{irr}_t(G) \text{ follows.} $$

**Case 2:** By increasing $d_{G_i}(u_i), u_i \in V_s$ by 1, the partial sum $\sum_{j=1}^{n} |d_{G_i}(u_j) - d(w_j)|$
$w_j \in V_h$
increases by exactly $h$. It changes the partial sum $\sum_{j=1}^{n} |d_{G_i}(u_j) - d(w_j)|$ by exactly $(m-1)-l$ and
$w_j \in V_s$
finally it increases the the partial sum $\sum_{j=1}^{n} |d_{G_i}(u_j) - d(w_j)|$ by exactly $t$. Hence, the result,
$w_j \in V_t$
$$ \text{irr}_t(G^{u,v_1}) = \text{irr}_t(G) - (h-1) + s - t + h + (m-1) - l + t = \text{irr}_t(G) + 2m \text{ follows.} $$

**Case 3:** By increasing $d_{G_i}(u_i), v_i \in V_t$ by 1, the partial sum $\sum_{j=1}^{n} |d_{G_i}(u_j) - d(w_j)|$ decreases by
$w_j \in V_t$
exactly $h$. It decreases the partial sum $\sum_{j=1}^{n} |d_{G_i}(u_j) - d(w_j)|$ by exactly $s$ and finally it changes
$w_j \in V_t$
the the partial sum $\sum_{j=1}^{n} |d_{G_i}(u_j) - d(w_j)|$ by exactly $(m_1-1) - l_1$.
$w_j \in V_t$
$$ \text{irr}_t(G^{u,v_1}) = \text{irr}_t(G) - (h-1) + s - t - (h-1) - 2 - s + (m_1-1) - l_1 = \text{irr}_t(G) - 2(h + l_1) \text{ follows.} \quad \square $$

Hence, the result $\text{irr}_t(G^{u,v_1}) = \text{irr}_t(G) - (h-1) + s - t - (h-1) - 2 - s + (m_1-1) - l_1 = \text{irr}_t(G) - 2(h + l_1)$ follows. $\square$

It is to be noted Theorem 3.2 provides an alternate proof for the following that lemma provided in Zhu et al. (in press).

**LEMMA 3.3** (Zhu et al., in press) Let $G'$ be the graph obtained from $G$ by branch-transformation from $u$ to $v$. Then $\text{irr}_t(G) > \text{irr}_t(G')$.

Theorem 3.2 can be extended to multi graphs also as explained in the following result.

**COROLLARY 3.4** If multiple edges or loops are allowed in the graph or if edge-transformation is performed in a simple graph without a cut edge to give $G_{w_j \in G}^{w_j, v_1}$, then we have

$$ \text{irr}_t(G^{u,v_1}) = \begin{cases} \text{irr}_t(G), & \text{if } d_{G_i}(u_i) = d_{G_i}(u_1) - 1, \\ \text{irr}_t(G) + 2m, & \text{if } d_{G_i}(u_i) > d_{G_i}(u_1) - 1, \\ \text{irr}_t(G) - 2(h + l_1), & \text{if } d_{G_i}(u_i) < d_{G_i}(u_1) - 1. \end{cases} $$

*Proof* The proof of this theorem follows immediately as a consequence of Theorem 3.2. $\square$

## 4. Total irregularities of directed graphs

In this section, we extend the concept of total irregularities of graphs mentioned in above sections to directed graphs. Since the edges of a digraph $D$ are directed edges and the vertices of $D$ has two types of degrees, in-degrees and out-degrees, we need to define two types of total irregularities for a digraph, which are called total in-degree irregularities and total out-degree irregularities.

Let the vertices of a simple directed graph $D^-$ on $n$ vertices be labelled as $v_i; i = 1, 2, 3, \dots, n$ and let $d_{D^-}^+(v_i) = d^+(v_i)$ and $d_{D^-}^-(v_i) = d^-(v_i)$. Then, the notion of total in-irregularity of a given directed graph is introduced as follows.

**Definition 4.1** The total in-irregularity of a directed graph $D$ with respect to the in-degree of all vertices of $D$, denoted by $\text{irr}_t^-(D^-)$, is defined as $\text{irr}_t^-(D^-) = \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} |d^-(v_i) - d^-(v_j)| = \sum_{i=1}^{n} \sum_{j=i+1}^{n} |d^-(v_i) - d^-(v_j)|$
$$ \text{or } \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} |d^{-}(v_i) - d^{-}(v_j)|. $$

Similarly, the total out-irregularity of a digraph can also be defined as follows.

**Definition 4.2** The total out-irregularity of a directed graph $D$ with respect to the out-degree of all vertices of $D$, denoted by $irr_t^+(D^-)$, is defined as $irr_t^+(G^-) = \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n |d^+(v_i) - d^+(v_j)| = \sum_{i=1}^n \sum_{j=i+1}^n |d^+(v_i) - d^+(v_j)|$ or $\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} |d^+(v_i) - d^+(v_j)|$.

Re-orientation of an arc or arc-transformation of an arc will find application in most classical applications of directed graphs like tournaments, transportation problems, flow analysis or alike.

## 4.1. Total irregularities of directed paths and cycles

The total in-irregularity and the total out-irregularity of a directed path are determined in the following proposition.

**Proposition 4.3** For a directed path $P_n^-$ which is consecutively directed from left to right for which vertices $v_1, v_n$ are called the start-vertex and the end-vertex, respectively, we have

$$ (i) \quad irr_t^-(P_n^-) = irr_t^+(P_n^-) = n-1, $$

$$ (ii) \quad irr_t^-(P_n^-) = \begin{cases} n-1, & \text{if the orientation of } (v_1, v_2) \text{ is reversed,} \\ 3n-5, & \text{if the orientation of } (v_i, v_{i+1}), 2 \le i \le (n-1) \\ & \text{is reversed} \end{cases} $$

$$ (iii) \quad irr_t^+(P_n^-) = \begin{cases} n-1, & \text{if the orientation of } (v_{n-1}, v_n) \text{ is reversed,} \\ 3n-5, & \text{if the orientation of } (v_i, v_{i+1}), i \le n-2 \\ & \text{is reversed.} \end{cases} $$

*Proof* The proof is obvious from the definition of total in-irregularity and total out-irregularity of a given digraph. □

The total in-irregularity and the total out-irregularity of a directed cycle are determined in the following proposition.

**Proposition 4.4** For a directed cycle $C_n^-$ which is consecutively directed clockwise we have

$$ (i) \quad irr_t^-(C_n^-) = irr_t^+(C_n^-) = 0, $$

$$ (ii) \quad irr_t^-(C_n^-) = irr_t^+(C_n^-) = 2(n-1), \text{ if we reverse the orientation of any arc.} $$

*Proof* The proof is obvious from the definition of total in-irregularity and total out-irregularity of a given digraph. □

Through a simple change of Definition 3.1 the in-arc-transformation partitioning in respect of $v_1$ and the out-arc-transformation partitioning in respect of $v_1$ can be defined.

**Definition 4.5** The in-arc-transformation partitioning with respect to a vertex $v_i$ of the vertex set $V(G)$ of a simple connected directed graph $G^-$ on $n$ vertices is defined to be $V_h = \{v_i:d^-(v_i) = (d^-(v_1) - 1)\} \cup \{v_1\}, h = |V_h|$, and $V_s = \{v_i:d^-(v_i) > (d^-(v_1) - 1)\}, s = |V_s|$ and $V_t = \{v_i:d^-(v_i) < (d^-(v_1) - 1)\}, t = |V_t|$.
In view of Definition 4.5, we define some vertex sets of a given digraph are defined as follows.

$$ (i) \quad V_{s_1} = \{v_j : d^{-}(v_j) \le d^{-}(v_i), v_j \in V_s\}, m = |V_{s_1}| $$

$$ (ii) \quad V_{s_2} = \{v_j : d^{-}(v_j) > d^{-}(v_i), v_j \in V_s\}, l = |V_{s_2}| $$

$$ (iii) \quad V_{t_1} = \{v_j : d^{-}(v_j) \le d^{-}(v_i), v_j \in V_t\}, m_1 = |V_{t_1}| $$

$$ (iv) \quad V_{t_2} = \{v_j : d^{-}(v_j) > d^{-}(v_i), v_j \in V_t\}, l_1 = |V_{t_2}| $$

**Definition 4.6** The out-arc-transformation partitioning with respect to a vertex $v_i$ of the vertex set $V(G)$ of a simple connected directed graph $G$ on $n$ vertices is defined to be $V_h^* = \{v_i : d^+(v_i) = (d^+(v_1) - 1)\} \cup \{v_i\}, h^* = |V_h^*|$, and $V_s^* = \{v_i : d^+(v_i) > (d^+(v_1) - 1)\}, s^* = |V_s^*|$ and $V_t^* = \{v_i : d^+(v_i) < (d^+(v_1) - 1)\}, t^* = |V_t^*|$.

In view of Definition 4.5, we define some vertex sets of a given digraph are defined as follows.

$$ (i) \quad V_{s_1}^* = \{v_j : d^+(v_j) \le d^+(v_i), v_j \in V_s\}, m^* = |V_{s_1}^*| $$

$$ (ii) \quad V_{s_2}^* = \{v_j : d^+(v_j) > d^+(v_i), v_j \in V_s\}, l^* = |V_{s_2}^*| $$

$$ (iii) \quad V_{t_1}^* = \{v_j : d^+(v_j) \le d^+(v_i), v_j \in V_t\}, m_1^* = |V_{t_1}^*| $$

$$ (iv) \quad V_{t_2}^* = \{v_j : d^+(v_j) > d^+(v_i), v_j \in V_t\}, l_1^* = |V_{t_2}^*| $$

Analogous to Theorem 3.2, we propose the following result.

**Proposition 4.7** Consider a simple connected directed graph $G$. After in-arc-transformation in respect of $v_1$ we have

$$ (i) \quad \operatorname{irr}_t^-(G^{\nu_1 u_1}) = \begin{cases} \operatorname{irr}_t^-(G), & \text{if } d^-(v_i) = d^-(v_1) - 1 \\ \operatorname{irr}_t^-(G) + 2m, & \text{if } d^-(v_i) > d^-(v_1) - 1, \\ \operatorname{irr}_t^-(G) - 2(h + l_1), & \text{if } d^-(v_i) < d^-(v_1) - 1 \end{cases} $$

and

$$ (ii) \quad \operatorname{irr}_t^+(G^{\nu_1 u_1}) = \begin{cases} \operatorname{irr}_t^+(G), & \text{if } d^+(v_i) = d^+(v_1) - 1, \\ \operatorname{irr}_t^+(G) + 2m^*, & \text{if } d^+(v_i) > d^+(v_1) - 1, \\ \operatorname{irr}_t^+(G) - 2(h^* + l_1^*), & \text{if } d^+(v_i) < d^+(v_1) - 1. \end{cases} $$

**Proof** The proof is similar to Theorem 3.2. □

<figure><img src="image_4.png" /></figure>

## 4.2. Total irregularities of directed complete graphs

In this section, we initiate a study on the two types of irregularities of directed complete graphs. Consider a complete undirected graph $K_n$ and label the vertices $v_1, v_2, v_3, \dots, v_n$. Assign direction the edges of $K_n$ to get a directed graph, with $K_n$ as its underlying graph, in such a way that the edge $v_i v_j$ becomes the arc $(v_i, v_j)$ of this directed graph if $i < j$. We denote this directed graph by $K_n^-$, The following lemma discusses the two types of irregularities of $K_n^-$.

**LEMMA 4.8** For the directed complete graph $K_n^-$, the total irregularities are given by
$$ \operatorname{irr}_t^+(K_n^-) = \operatorname{irr}_t^-(K_n^-) = \sum_{i=1}^{n-1} \sum_{j=1}^{i} j = \frac{1}{6} n(n^2 - 1). $$

**Proof** The orientation results in an in-degree sequence $(0, 1, 2, \dots, (n-1))$ and an out-degree sequence $(n-1, n-2, n-3, \dots, 0)$. Choose the $k$-th entry of the in-degree sequence. We know that the $k$-th term is given by $\sum_{j=k+1}^{n} |d^-(v_j) - d^-(v_i)| = \sum_{i=1}^{n-(k+1)} i$. Also, we have $\operatorname{irr}_t^-= \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} |d^-(v_i) - d^-(v_j)|$ and
hence $irr_t^-(K_n^-) = \sum_{i=1}^{n-1} i + \sum_{i=1}^{n-2} i + \dots + \sum_{i=1}^{n-(n-1)} i = \sum_{i=1}^{n-1} \sum_{j=1}^i j = \frac{1}{6}n(n^2-1)$. Furthermore, since the out-degree sequence is a mirror image of the in-degree sequence and $irr_t^+ = \sum_{i=1}^{n-1} \sum_{j=i+1}^n |d^+(v_i) - d^+(v_j)|$, the result follows similarly. □

A general application of this study can be the following.

Consider any connected undirected graph $G$ on $n$ vertices and label its vertices randomly by $v_1, v_2, v_3, \dots, v_n$. Assign direction to the edges of the graph $G$ to be arcs according to the condition mentioned above and refer to the directed graph as the *root directed graph*, $G_{\text{root-graph}}$. Then, calculate both $irr_t^+(G_{\text{root-graph}})$ and $irr_t^-(G_{\text{root-graph}})$. In a *derivative graph* $G_{\text{derivative}}$ identify all arcs which were re-oriented or subjected to arc-transformation and apply the applicable results to recursively determine the total in-irregularity and total out-irregularity.

Consider the complete bipartite graph $K_{(m,n)}$ and call the $m$ vertices in the first bipartition by *left-side vertices* and the $n$ vertices in the second bipartition by *right-side vertices*. Assign directions to the edges of $K_{(m,n)}$ strictly from *left-side vertices* to *right-side vertices* to obtain $K_{(m,n)}^{l \to r}$.

**Proposition 4.9** For the directed graph $K_{m,n}^{l \to r}$, we have $irr_t^-(K_{m,n}^{l \to r}) = m^2n$ and $irr_t^+(K_{m,n}^{l \to r}) = mn^2$.

*Proof* The orientation of the directed complete bipartite graph $K_{m,n}^{l \to r}$ results in the in-degree sequence $(0, 0, \dots, 0, m, m, \dots, m)$ and the out-degree sequence $(n, n, \dots, n, 0, 0, \dots, 0)$. Here, we have the following cases.

$$ \underbrace{m\text{-entries}}_{\text{m-entries}} \underbrace{n\text{-entries}}_{\text{n-entries}} $$

**Case 1:** For the above-mentioned in-degree sequence of $K_{m,n}^{l \to r}$, we have the sum $\sum_{i=1}^{(m+n)-1} \sum_{j=(i+1)}^{(m+n)} |d^-(v_i) - d^-(v_j)|$ results in the value $m$, $(mn)$ times and $0$, $((m+n) - 2)$ times. Hence, $irr_t^-(K_{(m,n)}^{l \to r}) = m^2n$.

**Case 2:** For the above-mentioned out-degree sequence of $K_{m,n}^{l \to r}$, we have the sum $\sum_{i=1}^{(m+n)-1} \sum_{j=(i+1)}^{(m+n)} |d^+(v_i) - d^+(v_j)|$ results in the value $n$, $(mn)$ times and $0$, $((m+n) - 2)$ times. Hence, $irr_t^+(K_{(1,n)}^{l \to r}) = mn^2$. This completes the proof. □

Invoking from Proposition 4.9, we note that for the directed bipartite graph $K_{1,n}^{l \to r}$, we have $irr_t^-(K_{1,n}^{l \to r}) = n$ and $irr_t^+(K_{(1,n)}^{l \to r}) = n^2$ and $irr_t^-(K_{m,1}^{l \to r}) = m^2$ and $irr_t^+(K_{m,1}^{l \to r}) = m$.

The following is a challenging and interesting problem in this context.

**Problem 4.10** Describe an efficient algorithm to determine $irr_t^-(G_{\text{derivative}})$ and $irr_t^+(G_{\text{derivative}})$ from $irr_t^-(G_{\text{root-graph}})$ and $irr_t^+(G_{\text{root-graph}})$.

## 5. Conclusion

In this paper, we have studied certain types of total irregularities of certain graphs and digraphs. More problems in this area still remain unsettled. More studies on different types of irregularities for different graph classes, graph operations, graph products and on certain associated graphs such as line graphs and total graphs of given graphs and digraphs remain open. All these facts indicate that there is a wide scope for further investigations in this area.
**Funding**

The authors received no direct funding for this research.

**Author details**

Johan Kok<fnref n="1" />

E-mail: kokkiek2@tshwane.gov.za

ORCID ID: http://orcid.org/0000-0001-9692-4053

Naduvath Sudev<fnref n="2" />

E-mail: sudevnk@gmail.com

ORCID ID: http://orcid.org/0000-0003-0106-1676

**Citation information**

Cite this article as: A study on total irregularities of certain graphs and digraphs, Johan Kok & Naduvath Sudev, Cogent Mathematics (2016), 3: 1179708.

**References**

Abdo, H., Brandt, S., & Dimitrov, D. (2014). The total irregularity of a graph. *Discrete Mathematics and Theoretical Computer Science*, 16, 201–206.

Abdo, H., Cohen, N., & Dimitrov, D. (in press). *Bounds and computation of irregularity of a graph*. Filomat.

Abdo, H., & Dimitrov, D. (2014). The total irregularity of a graph under graph operations. *Miskolc Mathematical Notes*, 15, 3–17.

Albertson, M. O. (1997). The irregularity of a graph. *Ars Combinatoria*, 46, 219–225.

Bondy, J. A., & Murty, U. S. R. (1976). *Graph theory with applications*. London: MacMillan.

Chartrand, G., & Lesniak, L. (2000). *Graphs and digraphs*. Boca Raton, FL: CRC Press.

Dimitrov, D., & Škrekovski, R. (2015). Comparing the irregularity and the total irregularity of graphs. *Ars Mathematica Contemporanea*, 9, 45–50.

Harary, F. (1969). *Graph theory*. New Delhi: New Age International.

Henning, M. A., & Rautenbach, D. (2007). On the irregularity of bipartite graphs. *Discrete Mathematics*, 307, 467–472.

Jensen, J. B., & Gutin, G. (2007). *Digraphs-theory, applications and algorithms*. Berlin: Springer-Verlag.

West, D. B. (2001). *Introduction to graph theory*. Delhi: Pearson Education.

Zhu, Y., You, L., & Yang, J. (in press). *The minimal total irregularity of graphs*. arXiv: 1404.0931v1.

<figure><img src="image_5.png" /></figure>

© 2016 The Author(s). This open access article is distributed under a Creative Commons Attribution (CC-BY) 4.0 license.

You are free to:

Share — copy and redistribute the material in any medium or format

Adapt — remix, transform, and build upon the material for any purpose, even commercially.

The licensor cannot revoke these freedoms as long as you follow the license terms.

Under the following terms:

Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made.

You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.

No additional restrictions

You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.

* Immediate, universal access to your article on publication

* High visibility and discoverability via the Cogent OA website as well as Taylor & Francis Online

* Download and citation statistics for your article

* Rapid online publication

* Input from, and dialog with, expert editors and editorial boards

* Retention of full copyright of your article

* Guaranteed legacy preservation of your article

* Discounts and waivers for authors in developing regions

<figure><img src="image_6.png" /></figure>

<footnote n="1">¹ Tshwane Metropolitan Police Department, City of Tshwane, Republic of South Africa.</footnote>

<footnote n="2">² Department of Mathematics, Vidya Academy of Science & Technology, Thalakkottukara, Thrissur 680501, India.</footnote>