![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
The total irregularity of a simple undirected graph G is denoted by and is defined as
. 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.
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 (Citation1976), Harary (Citation1969), West (Citation2001) and for digraph theory, we further refer to Chartrand and Lesniak (Citation2000) Jensen and Gutin (Citation2007). 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 (Citation1997) as follows.
Definition 1.1
(Albertson, Citation1997) The imbalance of an edge in a given graph G is defined as
. The total irregularity of a graph G, denoted by
, is defined as
.
If the vertices of a graph G on n vertices are labelled as , then the definition may be
or
. For a graph on a singular vertex (1-null graph or
), we define
. Clearly,
if and only if G is regular.
If an edge e is a cut-edge of the graph G and a component of 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 (CitationXXXX) as follows.
Definition 1.2
(Zhu et al., CitationXXXX) Let G be a graph with at least two pendant vertices. Without loss of generality, let u be a vertex of G with , T be a hanging tree of G connecting to u with
and v be a pendant vertex of G with
. Let
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
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 (Citation2014), Abdo, Cohen, and Dimitrov (Citationin press), Abdo and Dimitrov (Citation2014), Albertson (Citation1997), Dimitrov and Škrekovski (Citation2015), Henning and Rautenbach (Citation2007), Zhu et al. (CitationXXXX). 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 and
. Therefore,
. Hence, the total irregularity of G is given by
, where
,
and
and
.
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 , and is denoted by
.
Remark 2.2
It is to be noted that and
.
Let G be a graph on n vertices with two connected components and
whose vertex sets are
and
. We fix the vertices
from
and
from
. Now, we define the vertex subsets
;
and let
and
. Then, choose
and
, where
and
. Similarly, let
and
where
and
and choose
and
where
and
.
Define the variables ,
,
and
.
Theorem 2.3
Let G be a graph on n vertices with two connected components and
, where
and
. Let
. Then, we have
or
.
Proof
Clearly, for the graph , we have
with
and
.
By increasing by 1 we increase the partial sum
by exactly
. It also reduces the partial sum
by exactly b. It also increases the partial sum
by exactly
and decreases the partial sum
by exactly
. Furthermore, by increasing
by 1, we increase the partial sum
by exactly
. It also reduces the partial sum
by exactly d. It also increases the partial sum
by exactly
and decreases the partial sum
by exactly
.
Hence, we have an interim result as follows.
By substituting the variables and
as defined in Definition the final result is as follows.
, or;
, follows.
Clearly is edge dependent in general but we have the following Corollary.
Corollary 2.4
Let the degree sequence of graphs and
be
and
respectively. If
for some i, j and
for some k, l and
and
then,
.
Proof
Begin the proof by choosing any vertex degree value in the degree sequence of
and identify largest vertex index say, i for which
. Similarly, choose any vertex degree value
in the degree sequence of
and identify largest vertex index say, l for which
. Here, we have to consider the following cases.
Case-1: With respect to , set the values as follows.
(i) |
| ||||
(ii) |
| ||||
(iii) |
| ||||
(iv) |
| ||||
(v) |
| ||||
(vi) |
| ||||
(vii) |
| ||||
(viii) |
|
Case-2: In respect of , set the values as follows.
(i) |
| ||||
(ii) |
| ||||
(iii) |
| ||||
(iv) |
| ||||
(v) |
| ||||
(vi) |
| ||||
(vii) |
| ||||
(viii) |
|
Since Case-1 and Case-2 yield the same result, the result follows from Theorem 2.3.
An immediate consequence of Corollary 2.4 is that for regular graphs and
we have
is a constant. This result is proved in the following proposition.
Proposition 2.5
For the regular graphs on n, m vertices, respectively, with
we have
Proof
The proof follows immediately from Corollary 2.4.
We note that if and
are of equal k-regularity, then
is independent of the k- degree of the vertices.
3. Total irregularity due to edge-transformation
Consider a graph G on vertices and a cut edge
. Let
,
and
. Edge-transformation with respect to
will be the graph
obtained by deleting the edge
and adding the edge
for any
. We call
the master graph and
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 , is defined to be
and
, and
and
and
and
.
Invoking Definition 3.1, we now define certain vertex sets in G as given below. Let and
and
, and
and
and
, and
and
and
, and
and
and
.
In view of the above notions, we propose the following theorem.
Theorem 3.2
For a graph G with a cut edge , let
. After edge-transformation in respect of
we have
Proof
If , then reducing
by 1, reduces the partial sum
by exactly
. It increases the partial sum
by exactly s and finally it reduces the the partial sum
by exactly t.
Case 1: By increasing by 1, the partial sum
increases by exactly
. It decreases the partial sum
by exactly s and finally it increases the the partial sum
by exactly t. Hence, the result,
follows.
Case 2: By increasing by 1, the partial sum
increases by exactly h. It changes the partial sum
by exactly
and finally it increases the the partial sum
by exactly t. Hence, the result,
follows.
Case 3: By increasing by 1, the partial sum
decreases by exactly h. It decreases the partial sum
by exactly s and finally it changes the the partial sum
by exactly
.
Hence, the result follows.
It is to be noted Theorem 3.2 provides an alternate proof for the following that lemma provided in Zhu et al. (CitationXXXX).
Lemma 3.3
(Zhu et al., ZYY) Let be the graph obtained from G by branch-transformation from u to v. Then
.
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 then we have
Proof
The proof of this theorem follows immediately as a consequence of Theorem 3.2.
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 on n vertices be labelled as
and let
and
. 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 , is defined as
or
.
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 , is defined as
or
.
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 which is consecutively directed from left to right for which vertices
are called the start-vertex and the end-vertex, respectively, we have
(i) |
| ||||
(ii) | |||||
(iii) |
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 which is consecutively directed clockwise we have
(i) |
| ||||
(ii) |
|
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 and the out-arc-transformation partitioning in respect of
can be defined.
Definition 4.5
The in-arc-transformation partitioning with respect to a vertex of the vertex set V(G) of a simple connected directed graph
on n vertices is defined to be
, and
and
.
In view of Definition 4.5, we define some vertex sets of a given digraph are defined as follows.
(i) |
| ||||
(ii) |
| ||||
(iii) |
| ||||
(iv) |
|
Definition 4.6
The out-arc-transformation partitioning with respect to a vertex of the vertex set
of a simple connected directed graph
on n vertices is defined to be
, and
and
.
In view of Definition 4.5, we define some vertex sets of a given digraph are defined as follows.
(i) |
| ||||
(ii) |
| ||||
(iii) |
| ||||
(iv) |
|
Proposition 4.7
Consider a simple connected directed graph G. After in-arc-transformation in respect of we have
(i) |
| ||||
(ii) |
Proof
The proof is similar to Theorem 3.2.
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 and label the vertices
. Assign direction the edges of
to get a directed graph, with
as its underlying graph, in such a way that the edge
becomes the arc
of this directed graph if
. We denote this directed graph by
. The following lemma discusses the two types of irregularities of
.
Lemma 4.8
For the directed complete graph , the total irregularities are given by
.
Proof
The orientation results in an in-degree sequence and an out-degree sequence
. Choose the k-th entry of the in-degree sequence. We know that the k-th term is given by
. Also, we have
and hence
. Furthermore, since the out-degree sequence is a mirror image of the in-degree sequence and
, 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 . 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,
. Then, calculate both
and
. In a derivative graph
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 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
strictly from left-side vertices to right-side vertices to obtain
.
Proposition 4.9
For the directed graph , we have
and
.
Proof
The orientation of the directed complete bipartite graph results in the in-degree sequence
and the out-degree sequence
. Here, we have the following cases.
Case 1: For the above-mentioned in-degree sequence of , we have the sum
results in the value m, (mn times) and 0, (
times). Hence,
.
Case 2: For the above-mentioned out-degree sequence of , we have the sum
results in the value n, (mn times) and 0, (
) times). Hence,
. This completes the proof.
Invoking from Proposition 4.9, we note that for the directed bipartite graph , we have
and
and
and
.
The following is a challenging and interesting problem in this context.
Problem 4.10
Describe an efficient algorithm to determine and
from
and
.
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
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.
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., & \v{S}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–1472.
- 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.