A study on total irregularities of certain graphs and digraphs

Abstract

The total irregularity of a simple undirected graph G is denoted by $ir{r}_t(G)$ and is defined as $ir{r}_t(G)=\frac{1}{2}\sum _{u,v\in V(G)}|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.

Keywords:

• total irregularity
• branch-transformation
• edge-transformation
• edge-joint
• total in-irregularity
• total out-irregularity

AMS Subject Classifications:

• 05C07
• 05C20
• 05C38
• 05C75

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.

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 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 $ir{r}_t(G)$, is defined as $ir{r}_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_i,i=1,2,3,\dots ,n$, then the definition may be $ir{r}_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)|$. For a graph on a singular vertex (1-null graph or $K_1$), we define $ir{r}_t(G)=0$. Clearly, $ir{r}_t(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 (XXXX) as follows.

Definition 1.2

(Zhu et al., XXXX) 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^{\prime }$ 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^{\prime }$ a branch-transformation on G from vertex u to vertex v.

Certain studies on irregularities and total irregularities of given graphs and the properties 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. (XXXX). 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 $ir{r}_t(G)=ir{r}_t(G_1)+ir{r}_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\in V(G),v\in V(H)$, and is denoted by $G{⇝}_{uv}H$.

Remark 2.2

It is to be noted that $G{⇝}_{uv}H=G\cup H+uv$ and $G{⇝}_{uv}H\simeq H{⇝}_{vu}G$.

Let G be a graph on n vertices with two connected components $G_1$ and $G_2$ whose vertex sets are $V(G_1)=\{u_i:1\le i\le r\}$ and $V(G_2)=\{v_j:1\le j\le s\}$. We fix the vertices $u_1$ from $G_1$ and $v_1$ from $G_2$. Now, we define the vertex subsets $V_1=\{u_x:d_{G_1}(u_x)\le d_{G_1}(u_1),x\ne 1\}$; $V_2=\{u_y:d_{G_1}(u_y)>d_{G_1}(u_1)\}$ and let $|V_1|=a$ and $|V_2|=b$. Then, choose $V_3=\{v_x:d_{G_2}(v_x)\le d_{G_1}(u_1)\}$ and $V_4=\{v_y:d_{G_2}(v_y)>d_{G_1}(u_1)\}$, where $|V_3|=a^{\ast }$ and $|V_4|=b^{\ast }$. Similarly, let $V_5=\{v_z:d_{G_2}(v_z)\le d_{G_2}(v_1),z\ne 1\}$ and $V_6=\{v_w:d_{G_2}(v_w)>d_{G_2}(v_1)\}$ where $|V_5|=c$ and $|V_6|=d$ and choose $V_7=\{u_z:d_{G_1}(u_z)\le d_{G_2}(v_1)\}$ and $V_8=\{u_w:d_{G_1}(u_w)>d_{G_2}(v_1)\}$ where $|V_7|=c^{\ast }$ and $|V_8|=d^{\ast }$.

Define the variables $b=r-a$, $d=s-c=n-r-c$, $b^{\ast }=r-a^{\ast }$ and $d^{\ast }=s-c^{\ast }=n-r-c^{\ast }$.

Theorem 2.3

Let G be a graph on n vertices with two connected components $G_1$ and $G_2$, where $V(G_1)=\{u_i:1\le i\le r\}$ and $V(G_2)=\{v_j:1\le j\le s\}$ . Let $G^{\prime }=G_1{⇝}_{u_1{v}_1}{G}_2$. Then, we have $ir{r}_t(G^{\prime })=ir{r}_t(G_1)+ir{r}_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^{\ast }+d+d^{\ast })-2$ or $ir{r}_t(G^{\prime })=ir{r}_t(G_1)+ir{r}_t(G_2)+\sum _{i=1}^r\sum _{j=1}^s|d_{G_1}(u_i)-d_{G_2}(v_j)|+2(a+a^{\ast }+c+c^{\ast })-2n+2$.

Proof

Clearly, for the graph $G=G_1\cup G_2$, we have $ir{r}_t(G)=ir{r}_t(G_1)+ir{r}_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 _{\begin{array}{c}j=1w_j\in V_1\end{array}}^a|d_{G_1}(u_1)-d_{G_1}(w_j)|$ by exactly $(a-1)$. It also reduces the partial sum $\sum _{\begin{array}{c}j=1w_j\in V_2\end{array}}^b|d_{G_1}(u_1)-d_{G_1}(w_j)|$ by exactly b. It also increases the partial sum $\sum _{\begin{array}{c}j=1w_j\in V_3\end{array}}^{a^{\ast }}|d_{G_1}(u_1)-d_{G_2}(w_j)|$ by exactly $a^{\ast }$ and decreases the partial sum $\sum _{\begin{array}{c}j=1w_j\in V_4\end{array}}^{b^{\ast }}|d_{G_1}(u_1)-d_{G_2}(w_j)|$ by exactly $b^{\ast }$. Furthermore, by increasing $d_{G_2}(v_1)$ by 1, we increase the partial sum $\sum _{\begin{array}{c}j=1w_j\in V_5\end{array}}^c|d_{G_2}(v_1)-d_{G_2}(w_j)|$ by exactly $(c-1)$. It also reduces the partial sum $\sum _{\begin{array}{c}j=1w_j\in V_6\end{array}}^d|d_{G_1}(u_1)-d_{G_2}(w_j)|$ by exactly d. It also increases the partial sum $\sum _{\begin{array}{c}j=1w_j\in V_7\end{array}}^{c^{\ast }}|d_{G_1}(u_1)-d_{G_1}(w_j)|$ by exactly $c^{\ast }$ and decreases the partial sum $\sum _{\begin{array}{c}j=1w_j\in V_8\end{array}}^{d^{\ast }}|d_{G_1}(u_1)-d_{G_1}(w_j)|$ by exactly $d^{\ast }$.

Hence, we have an interim result as follows.$$\begin{array}{cc}\hfill ir{r}_t(G^{\prime })& =ir{r}_t(G_1)+ir{r}_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^{\ast }-b^{\ast }+(c-1)-d+c^{\ast }-d^{\ast }\hfill \\ \hfill & =ir{r}_t(G_1)+ir{r}_t(G_2)+\sum _{i=1}^r\sum _{j=1}^s|d_{G_1}(u_i)-d_{G_2}(v_j)|+(a-b)+(a^{\ast }-b^{\ast })+(c-d)+(c^{\ast }-d^{\ast })-2.\hfill \end{array}$$

By substituting the variables $b,d,b^{\ast }$ and $d^{\ast }$ as defined in Definition the final result is as follows.

$ir{r}_t(G^{\prime })=ir{r}_t(G_1)+ir{r}_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^{\ast }+d+d^{\ast })-2$, or; $ir{r}_t(G^{\prime })=ir{r}_t(G_1)+ir{r}_t(G_2)+\sum _{i=1}^r\sum _{j=1}^s|d_{G_1}(u_i)-d_{G_2}(v_j)|+2(a+a^{\ast }+c+c^{\ast })-2n+2$, follows. $\square$

Clearly $ir{r}_t(G^{\prime })$ 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^{\prime }=G_1{⇝}_{u_i{v}_l}{G}_2$ and $G^{″}=G_1{⇝}_{u_k{v}_j}{G}_2$ then, $ir{r}_t(G^{\prime })=ir{r}_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^{\prime }=G_1{⇝}_{u_i{v}_l}{G}_2$, set the values as follows.

(i)	$|V_1|=a=i-1$,
(ii)	$|V_2|=b=n-i$,
(iii)	$|V_3|=a^{\ast }=j$,
(iv)	$|V_4|=b^{\ast }=m-j$,
(v)	$|V_5|=c=l-1$,
(vi)	$|V_6|=d=m-l$,
(vii)	$|V_7|=c^{\ast }=k$,
(viii)	$|V_8|=d^{\ast }=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{⇝}_{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^{\ast }=l$,
(iv)	$|V_4|=b^{\ast }=m-l$,
(v)	$|V_5|=c=j-1$,
(vi)	$|V_6|=d=m-j$,
(vii)	$|V_7|=c^{\ast }=i$,
(viii)	$|V_8|=d^{\ast }=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 $ir{r}_t(G^{\prime })=ir{r}_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 $ir{r}_t{(G_1{⇝}_{vu}{G}_2)}_{\begin{array}{c}u\in V(G_1)v\in V(G_2)\end{array}}$ 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$$\begin{array}{c}\hfill ir{r}_t(G_1{⇝}_{uv}{G}_2)=\left\{\begin{array}{cc}2(n+m)-2,\hfill & \text{if}{d}_{G_1}(u)=d_{G_2}(v),\hfill \\ nm|d_{G_1}(u)-d_{G_2}(v)|+2(n-1),\hfill & \text{if}{d}_{G_1}(u)>d_{G_2}(v).\hfill \end{array}\right.\end{array}$$

Proof

The proof follows immediately from Corollary 2.4. $\square$

We note that if $G_1$ and $G_2$ are of equal k-regularity, then $ir{r}_t(G_1{⇝}_{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_1{v}_1$. Let $G=(G_1\cup G_2)+u_1{v}_1$, $u_1\in V(G_1)=\{u_i:1\le i\le l_1\}$ and $v_1\in V(G_2)=\{v_i:1\le i\le l_2\}$. Edge-transformation with respect to $u_1$ will be the graph $G^{u_i{v}_1}$ obtained by deleting the edge $u_1{v}_1$ and adding the edge $u_i{v}_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_1{v}_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_1}=\{u_j,v_k:d_{G_1}(u_j)\le d_{G_1}(u_i)$ and $d_{G_2}(v_k)\le d_{G_1}(u_i)$ 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)$ and $d_{G_2}(v_k)>d_{G_1}(u_i)$ 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)$ and $d_{G_2}(v_k)\le d_{G_1}(u_i)$ 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)$ and $d_{G_2}(v_k)>d_{G_1}(u_i)$ 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_1{v}_1$, let $G-u_1{v}_1=G_1\cup G_2$. After edge-transformation in respect of $v_1$ we have$$\begin{array}{c}\hfill ir{r}_t(G^{u_i{v}_1})=\left\{\begin{array}{cc}ir{r}_t(G),\hfill & \text{if}{d}_{G_1}(u_i)=d_{G_1}(u_1)-1,\hfill \\ ir{r}_t(G)+2m,\hfill & \text{if}{d}_{G_1}(u_i)>d_{G_1}(u_1)-1,\hfill \\ ir{r}_t(G)-2(h+l_1),\hfill & \text{if}{d}_{G_1}(u_i)<d_{G_1}(u_1)-1.\hfill \end{array}\right.\end{array}$$

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 _{\begin{array}{c}j=1w_j\in V_h\end{array}}^h|d_{G_1}(u_1)-d(w_j)|$ by exactly $(h-1)$. It increases the partial sum $\sum _{\begin{array}{c}j=1w_j\in V_s\end{array}}^s|d_{G_1}(u_1)-d(w_j)|$ by exactly s and finally it reduces the the partial sum $\sum _{\begin{array}{c}j=1w_j\in V_t\end{array}}^t|d_{G_1}(u_1)-d(w_j)|$ by exactly t.

Case 1: By increasing $d_{G_1}(u_i),u_i\in V_h$ by 1, the partial sum $\sum _{\begin{array}{c}j=1w_j\in V_h\end{array}}^h|d_{G_1}(u_i)-d(w_j)|$ increases by exactly $(h-1)$. It decreases the partial sum $\sum _{\begin{array}{c}j=1w_j\in V_s\end{array}}^s|d_{G_1}(u_i)-d(w_j)|$ by exactly s and finally it increases the the partial sum $\sum _{\begin{array}{c}j=1w_j\in V_t\end{array}}^t|d_{G_1}(u_i)-d(w_j)|$ by exactly t. Hence, the result, $ir{r}_t(G^{u_i{v}_1})=ir{r}_t(G)-(h-1)+s-t+((h-1)-s+t)=ir{r}_t(G)$ follows.

Case 2: By increasing $d_{G_1}(u_i),u_i\in V_s$ by 1, the partial sum $\sum _{\begin{array}{c}j=1w_j\in V_h\end{array}}^h|d_{G_1}(u_i)-d(w_j)|$ increases by exactly h. It changes the partial sum $\sum _{\begin{array}{c}j=1w_j\in V_s\end{array}}^s|d_{G_1}(u_i)-d(w_j)|$ by exactly $(m-1)-l$ and finally it increases the the partial sum $\sum _{\begin{array}{c}j=1w_j\in V_t\end{array}}^t|d_{G_1}(u_i)-d(w_j)|$ by exactly t. Hence, the result, $ir{r}_t(G^{u_i{v}_1})=ir{r}_t(G)-(h-1)+s-t+h+(m-1)-l+t=ir{r}_t(G)+2m$ follows.

Case 3: By increasing $d_{G_1}(u_i),v_i\in V_t$ by 1, the partial sum $\sum _{\begin{array}{c}j=1w_j\in V_t\end{array}}^h|d_{G_1}(u_i)-d(w_j)|$ decreases by exactly h. It decreases the partial sum $\sum _{\begin{array}{c}j=1w_j\in V_t\end{array}}^s|d_{G_1}(u_i)-d(w_j)|$ by exactly s and finally it changes the the partial sum $\sum _{\begin{array}{c}j=1w_j\in V_t\end{array}}^t|d_{G_1}(u_i)-d(w_j)|$ by exactly $(m_1-1)-l_1$.

Hence, the result $ir{r}_t(G^{u_i{v}_1})=ir{r}_t(G)-(h-1)+s-t-(h-1)-2-s+(m_1-1)-l_1=ir{r}_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. (XXXX).

Lemma 3.3

(Zhu et al., ZYY) Let $G^{\prime }$ be the graph obtained from G by branch-transformation from u to v. Then $ir{r}_t(G)>ir{r}_t(G^{\prime })$.

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_i\in G}^{w_i{v}_1},$ then we have$$\begin{array}{c}\hfill ir{r}_t(G^{u_i{v}_1})=\left\{\begin{array}{cc}ir{r}_t(G),\hfill & \text{if}{d}_{G_1}(u_i)=d_{G_1}(u_1)-1,\hfill \\ ir{r}_t(G)+2m,\hfill & \text{if}{d}_{G_1}(u_i)>d_{G_1}(u_1)-1,\hfill \\ ir{r}_t(G)-2(h+l_1),\hfill & \text{if}{d}_{G_1}(u_i)<d_{G_1}(u_1)-1.\hfill \end{array}\right.\end{array}$$

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^{\to }$ on n vertices be labelled as $v_i;i=1,2,3,\dots ,n$ and let $d_{D^{\to }}^{+}(v_i)=d^{+}(v_i)$ and $d_{D^{\to }}^{-}(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 $ir{r}_t^{-}(D^{\to })$, is defined as $ir{r}_t^{-}(D^{\to })=\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)|$.

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 $ir{r}_t^{+}(D^{\to })$, is defined as $ir{r}_t^{+}(G^{\to })=\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^{\to }$ 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)	$ir{r}_t^{-}(P_n^{\to })=ir{r}_t^{+}(P_n^{\to })=n-1$,
(ii)	$$\begin{array}{c}\hfill ir{r}_t^{-}(P_n^{\to })=\left\{\begin{array}{cc}n-1,\hfill & \text{if the orientation of}(v_1,v_2)\text{is reversed},\hfill \\ 3n-5,\hfill & \text{if the orientation of}(v_i,v_{i+1}),2\le i\le (n-1)\hfill \\ \hfill & \text{is reversed}\hfill \end{array}\right.\end{array}$$
(iii)	$$\begin{array}{c}\hfill ir{r}_t^{+}(P_n^{\to })=\left\{\begin{array}{cc}n-1,\hfill & \text{if the orientation of}(v_{n-1},v_n)\text{is reversed},\hfill \\ 3n-5,\hfill & \text{if the orientation of}(v_i,v_{i+1}),\le i\le n-2\hfill \\ \hfill & \text{is reversed}.\hfill \end{array}\right.\end{array}$$

Proof

The proof is obvious from the definition of total in-irregularity and total out-irregularity of a given digraph. $\square$

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^{\to }$ which is consecutively directed clockwise we have

(i)	$ir{r}_t^{-}(C_n^{\to })=ir{r}_t^{+}(C_n^{\to })=0$,
(ii)	$ir{r}_t^{-}(C_n^{\to })=ir{r}_t^{+}(C_n^{\to })=2(n-1)$, 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. $\square$

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^{\to }$ 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)	$V_{s_1}=\{v_j:d^{-}(v_j)\le d^{-}(v_i),v_j\in V_s\},m=|V_{s_1}|$,
(ii)	$V_{s_2}=\{v_j:d^{-}(v_j)>d^{-}(v_i),v_j\in V_s\},l=|V_{s_2}|$,
(iii)	$V_{t_1}=\{v_j:d^{-}(v_j)\le d^{-}(v_i),v_j\in V_t\},m_1=|V_{t_1}|$,
(iv)	$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^{\to })$ of a simple connected directed graph $G^{\to }$ on n vertices is defined to be $V_{h^{\ast }}=\{v_i:d^{+}(v_i)=(d^{+}(v_1)-1)\}\cup \{v_1\},h^{\ast }=|V_{h^{\ast }}|$, and $V_{s^{\ast }}=\{v_i:d^{+}(v_i)>(d^{+}(v_1)-1)\},s^{\ast }=|V_{s^{\ast }}|$ and $V_{t^{\ast }}=\{v_i:d^{+}(v_i)<(d^{+}(v_1)-1)\},t^{\ast }=|V_{t^{\ast }}|$.

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

(i)	$V_{s_1^{\ast }}=\{v_j:d^{+}(v_j)\le d^{+}(v_i),v_j\in V_s\},m^{\ast }=|V_{s_1^{\ast }}|$,
(ii)	$V_{s_2^{\ast }}=\{v_j:d^{+}(v_j)>d^{+}(v_i),v_j\in V_s\},l^{\ast }=|V_{s_2^{\ast }}|$,
(iii)	$V_{t_1^{\ast }}=\{v_j:d^{+}(v_j)\le d^{+}(v_i),v_j\in V_t\},m_1^{\ast }=|V_{t_1^{\ast }}|$,
(iv)	$V_{t_2^{\ast }}=\{v_j:d^{+}(v_j)>d^{+}(v_i),v_j\in V_t\},l_1^{\ast }=|V_{t_2^{\ast }}|$.

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)	$$\begin{array}{c}\hfill ir{r}_t^{-}(G^{v_i{u}_1})=\left\{\begin{array}{cc}ir{r}_t^{-}(G),\hfill & \text{if}{d}^{-}(v_i)=d^{-}(v_1)-1\hfill \\ ir{r}_t^{-}(G)+2m,\hfill & \text{if}{d}^{-}(v_i)>d^{-}(v_1)-1,\hfill \\ ir{r}_t^{-}(G)-2(h+l_1),\hfill & \text{if}{d}^{-}(v_i)<d^{-}(v_1)-1\hfill \end{array}\right.\end{array}$$ and
(ii)	$$\begin{array}{c}\hfill ir{r}_t^{+}(G^{v_i{u}_1})=\left\{\begin{array}{cc}ir{r}_t^{+}(G),\hfill & \text{if}{d}^{+}(v_i)=d^{+}(v_1)-1,\hfill \\ ir{r}_t^{+}(G)+2m^{\ast },\hfill & \text{if}{d}^{+}(v_i)>d^{+}(v_1)-1,\hfill \\ ir{r}_t^{+}(G)-2(h^{\ast }+l_1^{\ast }),\hfill & \text{if}{d}^{+}(v_i)<d^{+}(v_1)-1.\hfill \end{array}\right.\end{array}$$

Proof

The proof is similar to Theorem 3.2. $\square$

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^{\to }$. The following lemma discusses the two types of irregularities of $K_n^{\to }$.

Lemma 4.8

For the directed complete graph $K_n^{\to }$, the total irregularities are given by $ir{r}_t^{+}(K_n^{\to })=ir{r}_t^{-}(K_n^{\to })=\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_k)-d^{-}(v_j)|=\sum _{i=1}^{n-(k+1)}i$. Also, we have $ir{r}_t^{-}=\sum _{i=1}^{n-1}\sum _{j=i+1}^n|d^{-}(v_i)-d^{-}(v_j)|$ and hence $ir{r}_t^{-}(K_n^{\to })=\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 $ir{r}_t^{+}=\sum _{i=1}^{n-1}\sum _{j=i+1}^n|d^{+}(v_i)-d^{+}(v_j)|$, the result follows similarly. $\square$

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_{root-graph}^{\to }$. Then, calculate both $ir{r}_t^{+}(G_{root-graph}^{\to })$ and $ir{r}_t^{-}(G_{root-graph}^{\to })$. In a derivative graph $G_{derivative}^{\to }$ 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 $ir{r}_t^{-}(K_{m,n}^{l\to r})=m^{2}n$ and $ir{r}_t^{+}(K_{m,n}^{l\to r})=m{n}^2$.

Proof

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

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, $ir{r}_t^{-}(K_{(m,n)}^{l\to r})=m^{2}n$.

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, $ir{r}_t^{+}(K_{(1,n)}^{l\to r})=m{n}^2$. This completes the proof. $\square$

Invoking from Proposition 4.9, we note that for the directed bipartite graph $K_{1,n}^{l\to r}$, we have $ir{r}_t^{-}(K_{1,n}^{l\to r})=n$ and $ir{r}_t^{+}(K_{(1,n)}^{l\to r})=n^2$ and $ir{r}_t^{-}(K_{m,1}^{l\to r})=m^2$ and $ir{r}_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 $ir{r}_t^{-}(G_{derivative}^{\to })$ and $ir{r}_t^{+}(G_{derivative}^{\to })$ from $ir{r}_t^{-}(G_{root-graph}^{\to })$ and $ir{r}_t^{+}(G_{root-graph}^{\to })$.

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.

Additional information

Funding

The authors received no direct funding for this research.

Notes on contributors

Johan Kok

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

Naduvath Sudev has been working as a professor (sssociate) 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.