# The Maximal Total Irregularity of Bicyclic Graphs

Authors: Lihua You; Jieshan Yang; Yingxue Zhu; Zhifu You
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

In 2012, Abdo and Dimitrov defined the total irregularity of a graphG=(V,E) as irrtG=1/2∑u,v∈VdGu-dGv, where dGu denotes the vertex degree of a vertex u∈V. In this paper, we investigate the total irregularity of bicyclic graphs and characterize the graph with the maximal total irregularity among all bicyclic graphs on n vertices.


---

## Body

## 1. Introduction

LetG=(V,E) be a simple undirected graph with vertex set V and edge set E. For any vertices u,v∈V, the degree of v is denoted by dG(v), and the distance dG(u,v) is defined as the length of the shortest path between u and v in G. Let Pn, Cn, and Sn be the path, cycle, and star on n vertices, respectively.A graph is regular if all its vertices have the same degree; otherwise it is irregular. Several approaches that characterize how irregular a graph is have been proposed. In [1], Albertson defined the imbalance of an edge e=uv∈E as |dG(u)-dG(v)| and the irregularity of G as
(1)irr(G)=∑uv∈E‍|dG(u)-dG(v)|.
More results on the imbalance and the irregularity of a graph G can be found in [1–4].Inspired by the structure and meaning of (1), Abdo and Dimitrov [5] introduced a new irregularity measure, called the total irregularity. For a graph G, it is defined as
(2)irrt(G)=12∑u,v∈V‍|dG(u)-dG(v)|.Although the two irregularity measures capture the irregularity only by a single parameter, namely, the degree of a vertex, the new measure is more superior than the old one in some aspects. For example, (2) has an expected property of an irregularity measure that graphs with the same degree sequence have the same total irregularity, while (1) does not have. Both measures also have common properties, including that they are zero if and only if G is regular.Obviously,irrt(G) is an upper bound of irr(G). In [6], the authors derived relation between irrt(G) and irr(G) for a connected graph G with n vertices; that is, irrt(G)≤n2irr(G)/4. Furthermore, they showed that irrt(T)≤(n-2)irr(T) for any tree T.In [5], the authors obtained the upper bound of the total irregularity among all graphs with n vertices, and they showed that the star graph Sn is the tree with the maximal total irregularity among all trees with n vertices.Theorem 1 (see [5]).
LetG be a simple, undirected graph on n vertices. Then,(1)
irrt(G)≤(1/12)(2n3-3n2-2n+3).(2)
IfG is a tree, then irrt(G)≤(n-1)(n-2), with equality holds if and only if G≅Sn.In [7], the authors investigated the total irregularity of unicyclic graphs and determined the graph with the maximal total irregularity n2-n-6 among unicyclic graphs on n vertices. In [8], the authors investigated the minimal total irregularity of graphs, and they characterized the graph with the minimal, the second minimal, the third minimal total irregularity among trees, unicyclic graphs or bicyclic graphs on n vertices.Recently, Abdo and Dimitrov [9] also obtained the upper bounds on the total irregularity of graphs under several graph operations including join, lexicographic product, Cartesian product, strong product, direct product, corona product, disjunction, and symmetric difference.In this paper, we introduce two transformations to study the total irregularity of bicyclic graphs in Section2 and characterize the graph with the maximal total irregularity n2+n-16 among all bicyclic graphs on n vertices in Section 3.


## 2. Some Preliminaries and Two Transformations

In this section, we introduce some definitions, notations, two transformations, and basic properties which we need to use in the proofs of the main results. Other undefined notations may refer to [10].A bicyclic graph is a simple connected graph in which the number of edges equals the number of vertices plus one. There are two basic bicyclic graphs:∞-graph and Θ-graph. An ∞-graph, denoted by ∞(p,q,l) (see Figure 1), is obtained from two vertex-disjoint cycles Cp and Cq by connecting one vertex of Cp and one of Cq with a path Pl of length l-1 (in the case of l=1, identifying the above two vertices, see Figure 2) where p,q≥3 and l≥1; and a Θ-graph, denoted by θ(p,q,l) (see Figure 3), is a graph on p+q-l vertices with the two cycles Cp and Cq having l common vertices, where p,q≥3 and l≥2.Figure 1
The graph∞(p,q,l) with l≥3.Figure 2
The graph∞(p,q,1).Figure 3
The graphθ(p,q,l).In Figure1, let w1(w5) be the common vertex of Pl and Cp(Cq); w2∈V(Cp)∖{w1} and w3∈V(Pl)∖{w1,w5} if l≥3, w4∈V(Cq)∖{w5}.In Figure2, let w1=V(Cp)∩V(Cq), w2∈V(∞(p,q,1))∖V(Cq), and w3∈V(∞(p,q,1))∖V(Cp).In Figure3, let w1=z1, w2∈{x1,x2,…,xp-l}, w3∈{z2,…,zl-1} if l≥3,w4∈{y1,y2,…,yq-l}, and w5=zl.A rooted graph has one of its vertices, called the root, distinguished from the others. LetTi be a rooted tree with |V(Ti)|≥2 and root vi(1≤i≤k).Letℙ*={P∣Pis a rooted path with length at least one and the root is its starting vertex}, 𝕊*={S∣Sis a rooted star and the root is its center}, and ℙ𝕊*={P+S∣P∈ℙ* and S is a star}, where the rooted graph P+S is obtained by identifying the end vertex of P∈ℙ* with the center of a star S and the root of P+S is the root of P.To identify nonadjacent verticesx with y of a graph G is to replace these two vertices by a single vertex incident to all the edges which were incident in G to either x or y. Let G1 and G2 be two graphs: v1∈V(G1) and v2∈V(G2). The graph G=(G1,v1)Δ(G2,v2) denotes the graph resulting from identifying v1 with v2. Let x∈V(∞(p,q,l)), y∈V(θ(p,q,l)), and v be the root of the rooted tree T. Take ∞(p,q,l,T)=(∞(p,q,l),x)Δ(T,v) and θ(p,q,l,T)=(θ(p,q,l),y)Δ(T,v). For example, see Figure 4.Figure 4
Three graphs.


### 2.1.α-Transformation

α
-Transformation. Let G=(V,E) be a bicyclic graph obtained from ∞(p,q,l) (θ(p,q,l)) with k(≥1) rooted trees T1,…,Tk attached, and let u∈V be one of the maximal degree vertices of G and let w be any pendent vertex of G which is adjacent to vertex y(y≠u). Let G′ be the graph obtained from G by deleting the pendent edge yw and adding a pendent edge uw. We call the transformation from G to G′ an α-transformation on G. For example, see Figure 5.Figure 5
α-transformation.Remark 2.
Note that in Figure5, the edge yw∈E(Ti). In fact, yw∈E(Tj) for any j∈{1,…,k}.Lemma 3.
LetG=(V,E) be a bicyclic graph obtained from ∞(p,q,l)(θ(p,q,l)) with k(≥1) rooted trees T1,…,Tk attached, and let G′ be the graph obtained from G by α-transformation as above. Then, irrt(G)<irrt(G′).Proof.
Note that after theα-transformation on G, only the degrees of u and y have been changed; namely, dG′(u)=dG(u)+1, dG′(y)=dG(y)-1, and dG′(x)=dG(x) for any x∈V∖{u,y}. Clearly,
(3)|dG′(u)-dG′(y)|-|dG(u)-dG(y)|=2,∑x∈V∖{u,y}‍(|dG′(u)-dG′(x)|-|dG(u)-dG(x)|)=n-2,∑x∈V∖{u,y}‍(|dG′(y)-dG′(x)|-|dG(y)-dG(x)|)≥-(n-2)
because for any integer a, |a-1|-|a|={-1,ifa>0;1,ifa≤0. Then,
(4)irrt(G′)-irrt(G)=(|dG′(u)-dG′(y)|-|dG(u)-dG(y)|)+∑x∈V∖{u,y}‍(|dG′(u)-dG′(x)|-|dG(u)-dG(x)|)+∑x∈V∖{u,y}‍(|dG′(y)-dG′(x)|-|dG(y)-dG(x)|)≥2+(n-2)+(-n+2)>0.By Lemma3 and the definition of α-transformation, we have the following result.Lemma 4.
LetG=(V,E) be a bicyclic graph obtained from ∞(p,q,l)  (θ(p,q,l)) with k(≥1) rooted trees T1,…,Tk attached.(1)
If one cannot get a new graph fromG by α-transformation, then there exists some rooted tree T such that G≅∞(p,q,l,T)(G≅θ(p,q,l,T)), where T∈𝕊*∪ℙ𝕊*.(2)
LetG1 be the graph obtained from G by repeating α-transformation, and one cannot get other graphs from G1 by repeating α-transformation. Then there exists some rooted tree T such that G1≅∞(p,q,l,T)(G1≅θ(p,q,l,T)), where T∈𝕊*∪ℙ𝕊* and irrt(G)<irrt(G1).


### 2.2.β-Transformation

β
-Transformation. Let G=(V,E) be a bicyclic graph and G≅∞(p,q,l,T)(G≅θ(p,q,l,T)), where T∈𝕊*∪ℙ𝕊*, let v be the root of the unique rooted tree T, let u be a vertex of T and let u1, u2, …, ut(t≥1) be the pendent vertices adjacent to u. Let G′ be the graph obtained from G by deleting the pendent edges uu1, uu2, …, uut and adding pendent edges w1u1, w1u2, …, w1ut. We call the transformation from G to G′ a β-transformation on G. For example, see Figures 6–8.Figure 6
β-transformation on ∞(p,q,l,T) with T∈𝕊*.Figure 7
β-Transformation on ∞(p,q,l,T) with T∈ℙ𝕊*.Figure 8
β-Transformation on θ(p,q,l,T) where T∈𝕊*.Lemma 5.
LetG=∞(p,q,l,T)(G=θ(p,q,l,T)) be a bicyclic graph where T∈ℙ𝕊*, let v be the root of the unique rooted tree T, let u be a vertex of T and let u1, u2, …, ut(t≥1) be the pendent vertices adjacent to u. Let G′ be the graph obtained from G by β-transformation (e.g., see Figure 7). Then, irrt(G)<irrt(G′).Proof.
For convenience, letG=(V,E). Note that the root of the unique rooted tree, v, is not necessarily different with w1. Clearly, we know that only the degrees of u and w1 have been changed after the β-transformation; namely, dG′(u)=1, dG′(w1)=dG(w1)+dG(u)-1, and dG′(x)=dG(x) for any vertex x∈V∖{u,w1}. Let U=V∖{u,w1}. Note that l+t≥2; then we complete the proof by the following three cases.
Case
1  (2≤l+t≤3). In this case, dG(u)<dG(w1). It implies that the β-transformation on G is α-transformation t times on G. Then, irrt(G)<irrt(G′) by using Lemma 3  t times.
Case
2  (l+t≥4,t=1). The proof is similar to the proof of Case 1; thus, we omit it.
Case
3  (l+t≥4,t≥2). In this case, vertex u is one of the maximal degree vertices of G; namely, dG(u)≥dG(x) for any vertex x∈V∖{u}. Then,
(5)|dG′(u)-dG′(w1)|-|dG(u)-dG(w1)|=2d(w1)-2,∑x∈U‍|dG′(u)-dG′(x)|-∑x∈U‍|dG(u)-dG(x)|=2∑x∈U‍dG(x)-(n-2)(dG(u)+1).
Now we discuss∑x∈U|dG′(w1)-dG′(x)|-∑x∈U|dG(w1)-dG(x)| as follows.
Subcase
3.1  (t≥2,l≥2). Because dG(w1)-dG(w5)-|dG(w1)-dG(w5)|={-2,ifv=w5;0,ifv≠w5, and dG(w1)≥dG(x) for any x∈U∖{w5}, then
(6)∑x∈U‍|dG′(w1)-dG′(x)|-∑x∈U‍|dG(w1)-dG(x)|=∑x∈U∖{w5}‍(dG(w1)+dG(u)-1-dG(x))-∑x∈U∖{w5}‍(dG(w1)-dG(x))+(dG(w1)+dG(u)-1-dG(w5))-|dG(w1)-dG(w5)|=(n-2)(dG(u)-1)+(dG(w1)-dG(w5))-|dG(w1)-dG(w5)|≥(n-2)(dG(u)-1)-2.
Subcase
3.2  (t≥3,l=1). Because dG(w1)≥dG(x) for any x∈U, then
(7)∑x∈U‍|dG′(w1)-dG′(x)|-∑x∈U‍|dG(w1)-dG(x)|=∑x∈U‍(dG(w1)+dG(u)-1-dG(x))-∑x∈U‍(dG(w1)-dG(x))=(n-2)(dG(u)-1).
Combining the above two subcases, we have(8)∑x∈U‍|dG′(w1)-dG′(x)|-∑x∈U‍|dG(w1)-dG(x)|≥(n-2)(dG(u)-1)-2.
BydG(w1)≥3 and dG(x)≥1 for any x∈U and the above arguments, we have
(9)irrt(G′)-irrt(G)=|dG′(u)-dG′(w1)|+∑x∈U‍|dG′(u)-dG′(x)|+∑x∈U‍|dG′(w1)-dG′(x)|-[|dG(u)-dG(w1)|+∑x∈U‍|dG(u)-dG(x)|mm+∑x∈U‍|dG(w1)-dG(x)|]≥2dG(w1)-2+2∑x∈U‍dG(x)-(n-2)(dG(u)+1)+(n-2)(dG(u)-1)-2≥2.LetG=∞(p,q,l,T) (G=θ(p,q,l,T)) be a bicyclic graph, let wi∈V(G)=V(i=1,…,5) as defined in Figures 1–3, and let u be the root of T. Take
(10)∞i(p,q,l,T)=(∞(p,q,l),wi)Δ(T,u),wherel≥2,i∈{1,2,3,4,5},∞j(p,q,1,T)=(∞(p,q,1),wj)Δ(T,u),wherej∈{1,2,3},θr(p,q,l,T)=(θ(p,q,l),wr)Δ(T,u),wherer∈{1,2,3,4,5}.Clearly,θ1(p,q,l,T)≅θ5(p,q,l,T).Lemma 6.
LetG=∞(p,q,l,T)(G=θ(p,q,l,T)) be a bicyclic graph, where T∈𝕊* and G≠∞1(p,q,l,T)(G≠θ1(p,q,l,T)), let u be the root of the unique rooted tree T, and let u1, u2, …, ut(t≥1) be the pendent vertices adjacent to u. Let G′ be the graph obtained from G by β-transformation (e.g., see Figures 6 and 8). Then,(1)
G′=∞1(p,q,l,T)(G′=θ1(p,q,l,T)).(2)
irrt(G)≤irrt(G′), and the equality holds if and only if G=∞5(p,q,l,T)  (G=θ5(p,q,l,T)).Proof.
Clearly,u≠w1, since G≠∞1(p,q,l,T)(G≠θ1(p,q,l,T)).
By the definition ofβ-transformation, (1) is obvious. Now we show that (2) holds.
Ifu=w5 when l≥2, namely, G=∞5(p,q,l,T)  (G=θ5(p,q,l,T)), then G and G′ have the same degree sequence; thus they have the same total irregularity: irrt(G)=irrt(G′).
Hence, we assumeu∉{w1,w5} in the following. Note that only the degrees of vertices u and w1 have been changed after the β-transformation; namely, dG′(u)=2, dG′(w1)=dG(w1)+dG(u)-2, and dG′(x)=dG(x) for any vertex x∈V∖{u,w1}. Let U=V∖{u,w1}. Note that l+t≥2; then we complete the proof by the following two cases.
Case
1  (l+t≥3). In this case, vertex u is one of the maximal degree vertices of G; namely, dG(u)≥dG(x) for any vertex x∈V∖{u} and dG(w1)≥dG(x) for any x∈U. Then,
(11)|dG′(u)-dG′(w1)|-|dG(u)-dG(w1)|=2dG(w1)-4,∑x∈U‍|dG′(w1)-dG′(x)|-∑x∈U‍|dG(w1)-dG(x)|=(n-2)(dG(u)-2),∑x∈U‍|dG′(u)-dG′(x)|-∑x∈U‍|dG(u)-dG(x)|=∑x∈U‍[|dG(x)-2|-(dG(u)-dG(x))]≥t+∑x∈U‍dG(x)-(n-2)dG(u).
BydG(w1)≥3 and t=dG(u)-2≥1 and the above arguments, we have
(12)irrt(G′)-irrt(G)=|dG′(u)-dG′(w1)|+∑x∈U‍|dG′(u)-dG′(x)|+∑x∈U‍|dG′(w1)-dG′(x)|-[|dG(u)-dG(w1)|+∑x∈U‍|dG(u)-dG(x)|mmm+∑x∈U‍|dG(w1)-dG(x)|]≥(2dG(w1)-4)+(n-2)(dG(u)-2)+t+∑x∈U‍dG(x)-(n-2)dG(u)≥2.
Case
2  (l+t=2). In this case, dG(u)<dG(w1). It implies that the β-transformation on G is α-transformation 1 time on G. Then, irrt(G)<irrt(G′) by Lemma 3.By the proof of Lemma6, we obtain the following result.Corollary 7.
LetT∈𝕊*. Then,(1)
irrt(∞1(p,q,l,T))=irrt(∞5(p,q,l,T))=max⁡{irrt(∞1(p,q,l,T)),…,irrt(∞5(p,q,l,T))}, where l≥2.(2)
irrt(∞1(p,q,1,T))=max⁡{irrt(∞1(p,q,1,T)), irrt(∞2(p,q,1,T)), irrt(∞3(p,q,1,T))}.(3)
irrt(θ1(p,q,l,T))=irrt(θ5(p,q,l,T))=max⁡{irrt(θ1(p,q,l,T)),…,irrt(θ5(p,q,l,T))}.


## 2.1.α-Transformation

α
-Transformation. Let G=(V,E) be a bicyclic graph obtained from ∞(p,q,l) (θ(p,q,l)) with k(≥1) rooted trees T1,…,Tk attached, and let u∈V be one of the maximal degree vertices of G and let w be any pendent vertex of G which is adjacent to vertex y(y≠u). Let G′ be the graph obtained from G by deleting the pendent edge yw and adding a pendent edge uw. We call the transformation from G to G′ an α-transformation on G. For example, see Figure 5.Figure 5
α-transformation.Remark 2.
Note that in Figure5, the edge yw∈E(Ti). In fact, yw∈E(Tj) for any j∈{1,…,k}.Lemma 3.
LetG=(V,E) be a bicyclic graph obtained from ∞(p,q,l)(θ(p,q,l)) with k(≥1) rooted trees T1,…,Tk attached, and let G′ be the graph obtained from G by α-transformation as above. Then, irrt(G)<irrt(G′).Proof.
Note that after theα-transformation on G, only the degrees of u and y have been changed; namely, dG′(u)=dG(u)+1, dG′(y)=dG(y)-1, and dG′(x)=dG(x) for any x∈V∖{u,y}. Clearly,
(3)|dG′(u)-dG′(y)|-|dG(u)-dG(y)|=2,∑x∈V∖{u,y}‍(|dG′(u)-dG′(x)|-|dG(u)-dG(x)|)=n-2,∑x∈V∖{u,y}‍(|dG′(y)-dG′(x)|-|dG(y)-dG(x)|)≥-(n-2)
because for any integer a, |a-1|-|a|={-1,ifa>0;1,ifa≤0. Then,
(4)irrt(G′)-irrt(G)=(|dG′(u)-dG′(y)|-|dG(u)-dG(y)|)+∑x∈V∖{u,y}‍(|dG′(u)-dG′(x)|-|dG(u)-dG(x)|)+∑x∈V∖{u,y}‍(|dG′(y)-dG′(x)|-|dG(y)-dG(x)|)≥2+(n-2)+(-n+2)>0.By Lemma3 and the definition of α-transformation, we have the following result.Lemma 4.
LetG=(V,E) be a bicyclic graph obtained from ∞(p,q,l)  (θ(p,q,l)) with k(≥1) rooted trees T1,…,Tk attached.(1)
If one cannot get a new graph fromG by α-transformation, then there exists some rooted tree T such that G≅∞(p,q,l,T)(G≅θ(p,q,l,T)), where T∈𝕊*∪ℙ𝕊*.(2)
LetG1 be the graph obtained from G by repeating α-transformation, and one cannot get other graphs from G1 by repeating α-transformation. Then there exists some rooted tree T such that G1≅∞(p,q,l,T)(G1≅θ(p,q,l,T)), where T∈𝕊*∪ℙ𝕊* and irrt(G)<irrt(G1).


## 2.2.β-Transformation

β
-Transformation. Let G=(V,E) be a bicyclic graph and G≅∞(p,q,l,T)(G≅θ(p,q,l,T)), where T∈𝕊*∪ℙ𝕊*, let v be the root of the unique rooted tree T, let u be a vertex of T and let u1, u2, …, ut(t≥1) be the pendent vertices adjacent to u. Let G′ be the graph obtained from G by deleting the pendent edges uu1, uu2, …, uut and adding pendent edges w1u1, w1u2, …, w1ut. We call the transformation from G to G′ a β-transformation on G. For example, see Figures 6–8.Figure 6
β-transformation on ∞(p,q,l,T) with T∈𝕊*.Figure 7
β-Transformation on ∞(p,q,l,T) with T∈ℙ𝕊*.Figure 8
β-Transformation on θ(p,q,l,T) where T∈𝕊*.Lemma 5.
LetG=∞(p,q,l,T)(G=θ(p,q,l,T)) be a bicyclic graph where T∈ℙ𝕊*, let v be the root of the unique rooted tree T, let u be a vertex of T and let u1, u2, …, ut(t≥1) be the pendent vertices adjacent to u. Let G′ be the graph obtained from G by β-transformation (e.g., see Figure 7). Then, irrt(G)<irrt(G′).Proof.
For convenience, letG=(V,E). Note that the root of the unique rooted tree, v, is not necessarily different with w1. Clearly, we know that only the degrees of u and w1 have been changed after the β-transformation; namely, dG′(u)=1, dG′(w1)=dG(w1)+dG(u)-1, and dG′(x)=dG(x) for any vertex x∈V∖{u,w1}. Let U=V∖{u,w1}. Note that l+t≥2; then we complete the proof by the following three cases.
Case
1  (2≤l+t≤3). In this case, dG(u)<dG(w1). It implies that the β-transformation on G is α-transformation t times on G. Then, irrt(G)<irrt(G′) by using Lemma 3  t times.
Case
2  (l+t≥4,t=1). The proof is similar to the proof of Case 1; thus, we omit it.
Case
3  (l+t≥4,t≥2). In this case, vertex u is one of the maximal degree vertices of G; namely, dG(u)≥dG(x) for any vertex x∈V∖{u}. Then,
(5)|dG′(u)-dG′(w1)|-|dG(u)-dG(w1)|=2d(w1)-2,∑x∈U‍|dG′(u)-dG′(x)|-∑x∈U‍|dG(u)-dG(x)|=2∑x∈U‍dG(x)-(n-2)(dG(u)+1).
Now we discuss∑x∈U|dG′(w1)-dG′(x)|-∑x∈U|dG(w1)-dG(x)| as follows.
Subcase
3.1  (t≥2,l≥2). Because dG(w1)-dG(w5)-|dG(w1)-dG(w5)|={-2,ifv=w5;0,ifv≠w5, and dG(w1)≥dG(x) for any x∈U∖{w5}, then
(6)∑x∈U‍|dG′(w1)-dG′(x)|-∑x∈U‍|dG(w1)-dG(x)|=∑x∈U∖{w5}‍(dG(w1)+dG(u)-1-dG(x))-∑x∈U∖{w5}‍(dG(w1)-dG(x))+(dG(w1)+dG(u)-1-dG(w5))-|dG(w1)-dG(w5)|=(n-2)(dG(u)-1)+(dG(w1)-dG(w5))-|dG(w1)-dG(w5)|≥(n-2)(dG(u)-1)-2.
Subcase
3.2  (t≥3,l=1). Because dG(w1)≥dG(x) for any x∈U, then
(7)∑x∈U‍|dG′(w1)-dG′(x)|-∑x∈U‍|dG(w1)-dG(x)|=∑x∈U‍(dG(w1)+dG(u)-1-dG(x))-∑x∈U‍(dG(w1)-dG(x))=(n-2)(dG(u)-1).
Combining the above two subcases, we have(8)∑x∈U‍|dG′(w1)-dG′(x)|-∑x∈U‍|dG(w1)-dG(x)|≥(n-2)(dG(u)-1)-2.
BydG(w1)≥3 and dG(x)≥1 for any x∈U and the above arguments, we have
(9)irrt(G′)-irrt(G)=|dG′(u)-dG′(w1)|+∑x∈U‍|dG′(u)-dG′(x)|+∑x∈U‍|dG′(w1)-dG′(x)|-[|dG(u)-dG(w1)|+∑x∈U‍|dG(u)-dG(x)|mm+∑x∈U‍|dG(w1)-dG(x)|]≥2dG(w1)-2+2∑x∈U‍dG(x)-(n-2)(dG(u)+1)+(n-2)(dG(u)-1)-2≥2.LetG=∞(p,q,l,T) (G=θ(p,q,l,T)) be a bicyclic graph, let wi∈V(G)=V(i=1,…,5) as defined in Figures 1–3, and let u be the root of T. Take
(10)∞i(p,q,l,T)=(∞(p,q,l),wi)Δ(T,u),wherel≥2,i∈{1,2,3,4,5},∞j(p,q,1,T)=(∞(p,q,1),wj)Δ(T,u),wherej∈{1,2,3},θr(p,q,l,T)=(θ(p,q,l),wr)Δ(T,u),wherer∈{1,2,3,4,5}.Clearly,θ1(p,q,l,T)≅θ5(p,q,l,T).Lemma 6.
LetG=∞(p,q,l,T)(G=θ(p,q,l,T)) be a bicyclic graph, where T∈𝕊* and G≠∞1(p,q,l,T)(G≠θ1(p,q,l,T)), let u be the root of the unique rooted tree T, and let u1, u2, …, ut(t≥1) be the pendent vertices adjacent to u. Let G′ be the graph obtained from G by β-transformation (e.g., see Figures 6 and 8). Then,(1)
G′=∞1(p,q,l,T)(G′=θ1(p,q,l,T)).(2)
irrt(G)≤irrt(G′), and the equality holds if and only if G=∞5(p,q,l,T)  (G=θ5(p,q,l,T)).Proof.
Clearly,u≠w1, since G≠∞1(p,q,l,T)(G≠θ1(p,q,l,T)).
By the definition ofβ-transformation, (1) is obvious. Now we show that (2) holds.
Ifu=w5 when l≥2, namely, G=∞5(p,q,l,T)  (G=θ5(p,q,l,T)), then G and G′ have the same degree sequence; thus they have the same total irregularity: irrt(G)=irrt(G′).
Hence, we assumeu∉{w1,w5} in the following. Note that only the degrees of vertices u and w1 have been changed after the β-transformation; namely, dG′(u)=2, dG′(w1)=dG(w1)+dG(u)-2, and dG′(x)=dG(x) for any vertex x∈V∖{u,w1}. Let U=V∖{u,w1}. Note that l+t≥2; then we complete the proof by the following two cases.
Case
1  (l+t≥3). In this case, vertex u is one of the maximal degree vertices of G; namely, dG(u)≥dG(x) for any vertex x∈V∖{u} and dG(w1)≥dG(x) for any x∈U. Then,
(11)|dG′(u)-dG′(w1)|-|dG(u)-dG(w1)|=2dG(w1)-4,∑x∈U‍|dG′(w1)-dG′(x)|-∑x∈U‍|dG(w1)-dG(x)|=(n-2)(dG(u)-2),∑x∈U‍|dG′(u)-dG′(x)|-∑x∈U‍|dG(u)-dG(x)|=∑x∈U‍[|dG(x)-2|-(dG(u)-dG(x))]≥t+∑x∈U‍dG(x)-(n-2)dG(u).
BydG(w1)≥3 and t=dG(u)-2≥1 and the above arguments, we have
(12)irrt(G′)-irrt(G)=|dG′(u)-dG′(w1)|+∑x∈U‍|dG′(u)-dG′(x)|+∑x∈U‍|dG′(w1)-dG′(x)|-[|dG(u)-dG(w1)|+∑x∈U‍|dG(u)-dG(x)|mmm+∑x∈U‍|dG(w1)-dG(x)|]≥(2dG(w1)-4)+(n-2)(dG(u)-2)+t+∑x∈U‍dG(x)-(n-2)dG(u)≥2.
Case
2  (l+t=2). In this case, dG(u)<dG(w1). It implies that the β-transformation on G is α-transformation 1 time on G. Then, irrt(G)<irrt(G′) by Lemma 3.By the proof of Lemma6, we obtain the following result.Corollary 7.
LetT∈𝕊*. Then,(1)
irrt(∞1(p,q,l,T))=irrt(∞5(p,q,l,T))=max⁡{irrt(∞1(p,q,l,T)),…,irrt(∞5(p,q,l,T))}, where l≥2.(2)
irrt(∞1(p,q,1,T))=max⁡{irrt(∞1(p,q,1,T)), irrt(∞2(p,q,1,T)), irrt(∞3(p,q,1,T))}.(3)
irrt(θ1(p,q,l,T))=irrt(θ5(p,q,l,T))=max⁡{irrt(θ1(p,q,l,T)),…,irrt(θ5(p,q,l,T))}.


## 3. The maximal Total Irregularity of Bicyclic Graphs

In this section, we will obtain the upper bound of the total irregularity among all bicyclic graphs onn vertices and characterize the extremal graph.Observe that any bicyclic graphG is obtained from an ∞-graph or a Θ-graph (possibly) by attaching trees to some of its vertices. Denoted by ℬn is the set of all bicyclic graphs on n vertices. Obviously, ℬn consists of three types of graphs: first type, denoted by Bn+, is the set of those graphs each of which is an ∞-graph, ∞(p,q,l), with trees attached when l=1; second type, denoted by Bn++, is the set of those graphs each of which is an ∞-graph, ∞(p,q,l), with trees attached when l≥2; third type, denoted by Θn, is the set of those graphs each of which is a Θ-graph, θ(p,q,l), with trees attached. Then, ℬn=Bn+∪Bn++∪Θn.


### 3.1. The Graph with the Maximal Total Irregularity inBn+

In this subsection, the bicyclic graph with the maximal total irregularity inBn+ is determined.Letn,p,q,r be positive integers with p,q≥3 and p+q+r-2=n; G=∞1(p,q,1,Sr). Clearly, the degree sequence of G is (r+3,2,…,2,1,…,1). By simple calculation, we have
(13)irrt(G)=(n-p-q+1)(n+p+q)+2p+2q-4.Theorem 8.
Letn,p,q,r be positive integers with p,q≥3 and p+q+r-2=n and let G∈Bn+ be a bicyclic graph on n vertices obtained from ∞(p,q,1) with k(≥1) rooted trees T1,…,Tk attached. Then, irrt(G)≤(n-p-q+1)(n+p+q)+2p+2q-4, and the equality holds if and only if G≅∞1(p,q,1,Sr).Proof.
Ifr=1, then n=p+q-1, and the rooted trees T1,…,Tk are trivial; namely, |V(Ti)|=1 with i=1,…,k. Then, G=∞(p,q,1)=∞1(p,q,1,S1) and irrt(G)=(n-p-q+1)(n+p+q)+2p+2q-4.
Ifr≥2, we complete the proof by the following three cases.
Case
1  (G≇∞(p,q,1,T)whereT∈𝕊*⋃‍ℙ𝕊*). Let G1 be the graph obtained from G by repeating α-transformation, and we cannot get a new graph from G1 by α-transformation. Then there exists a rooted tree T such that G1≅∞(p,q,1,T) where T∈𝕊*⋃‍ℙ𝕊* and irrt(G)<irrt(G1) by Lemma 4. Let u be the root of the rooted tree T.
Subcase
1.1  (G1≅∞(p,q,1,T)whereT∈𝕊*). If u=w1, then G1≅∞1(p,q,1,Sr) and irrt(G)<irrt(G1)=(n-p-q+1)(n+p+q)+2p+2q-4.
Ifu≠w1, then we can get a new graph G2≅∞1(p,q,1,Sr) by β-transformation on G1; thus irrt(G)<irrt(G1)<irrt(G2)=(n-p-q+1)(n+p+q)+2p+2q-4 by Lemma 6.
Subcase
1.2  (G1≅∞(p,q,1,T)whereT∈ℙ𝕊*). If u≠w1, let G2 be the graph obtained from G1 by β-transformation. Then irrt(G1)<irrt(G2) by Lemma 5. Repeating α-transformation on G2 until we cannot get a new graph, the resulting graph is G3≅∞1(p,q,1,Sr). By Lemma 4, irrt(G2)<irrt(G3) and thus irrt(G)<irrt(G1)<irrt(G2)<irrt(G3)=(n-p-q+1)(n+p+q)+2p+2q-4.
Ifu=w1 and dG1(u,v)=1, let G2 be the graph obtained from G1 by β-transformation; then G2≅∞1(p,q,1,Sr) and irrt(G)<irrt(G1)<irrt(G2)=(n-p-q+1)(n+p+q)+2p+2q-4 by Lemma 5.
Ifu=w1 and dG1(u,v)>1, Let G2 be the graph obtained from G1 by β-transformation and let G3 be the graph obtained from G2 by repeating α-transformation until we cannot get a new graph from G3 by α-transformation. Then by Lemmas 4 and 5, we know that G3≅∞1(p,q,1,Sr) and irrt(G)<irrt(G1)<irrt(G2)<irrt(G3)=(n-p-q+1)(n+p+q)+2p+2q-4.
Case
2  (G≅∞(p,q,1,T)whereT∈𝕊*).
The proof is similar to the proof of Subcase 1.1; thus, we omit it.
Case
3   (G≅∞(p,q,1,T)whereT∈ℙ𝕊*).
The proof is similar to the proof of Subcase 1.2; thus, we omit it.
Combining the above arguments, we complete the proof.Theorem 9.
Letp,q,r be positive integers with p,q≥3.(1)
Ifp≥4, then irrt(∞1(p,q,1,Sr))<irrt(∞1(p-1,q,1,Sr+1)).(2)
Ifq≥4, then irrt(∞1(p,q,1,Sr))<irrt(∞1(p,q-1,1,Sr+1)).Proof.
Clearly, the proofs of(1) and (2) are similar; we only show that (1) holds. Let n=p+q+r-2; by formula (13), we have irrt(∞1(p-1,q,1,Sr+1))-irrt(∞1(p,q,1,Sr))=2p+2q-4>0.Theorem 10.
Letn≥5 be a positive integer, and let G∈Bn+ be a bicyclic graph on n vertices. Then irrt(G)≤n2+n-22 and the equality holds if and only if G≅∞1(3,3,1,Sn-4) (see Figure 9).Figure 9
The graph∞1(3,3,1,Sn-4).Proof.
Letn,p,q,r be positive integers with p,q≥3 and p+q+r-2=n and let G∈Bn+ be a bicyclic graph on n vertices obtained from ∞(p,q,1) with k(≥1) rooted trees T1,…,Tk attached. Then by Theorem 8, we have irrt(G)≤(n-p-q+1)(n+p+q)+2p+2q-4, and the equality holds if and only if G≅∞1(p,q,1,Sr). Now we complete the proof by the following three cases.
Case
1  (p=q=3). Then, irrt(∞1(3,3,1,Sn-4))=n2+n-22.
Case
2  (p≥q≥3andp≥4). Then by using Theorem 9  p+q-6 times, we have irrt(∞1(p,q,1,Sr))<irrt(∞1(3,q,1,Sn-q-1))≤irrt(∞1(3,3,1,Sn-4)).
Case
3  (q≥p≥3andq≥4). The proof is similar to Case 2; thus, we omit it.


### 3.2. The Graph with the Maximal Total Irregularity inBn++

In this subsection, the bicyclic graph with the maximal total irregularity inBn++ is determined.Letn,p,q,r,l be positive integers with p,q≥3, l≥2, and p+q+r+l-3=n; G=∞1(p,q,1,Sr) or G=∞5(p,q,l,Sr). Clearly, the degree sequence of G is (r+2,3,2,…,2,1,…,1). By simple calculation, we have
(14)irrt(G)=(n-p-q-l+2)(n+p+q+l-1)+2p+2q+2l-8.Theorem 11.
Letn,p,q,l,r be positive integers with p,q≥3, l≥2, and p+q+r+l-3=n and let G∈Bn++ be a bicyclic graph on n vertices obtained from ∞(p,q,l) with k(≥1) rooted trees T1,…,Tk attached. Then, irrt(G)≤(n-p-q-l+2)(n+p+q+l-1)+2p+2q+2l-8, and the equality holds if and only if G≅∞1(p,q,l,Sr) or G≅∞5(p,q,l,Sr).Proof.
Ifr=1, then n=p+q+l-2, and the rooted trees T1,…,Tk are trivial; namely, |V(Ti)|=1 with i=1,…,k. Then, G=∞(p,q,l)=∞1(p,q,l,S1) and irrt(G)=(n-p-q-l+2)(n+p+q+l-1)+2p+2q+2l-8.
Ifr≥2, we complete the proof by the following three cases.
Case
1  (G≇∞(p,q,l,T)whereT∈𝕊*⋃‍ℙ𝕊*). Let G1 be the graph obtained from G by repeating α-transformation, and we cannot get a new graph from G1 by α-transformation. Then there exists a rooted tree T such that G1≅∞(p,q,l,T), where T∈𝕊*⋃‍ℙ𝕊* and irrt(G)<irrt(G1) by Lemma 4. Let u be the root of the rooted tree T.
Subcase
1.1  (G1≅∞(p,q,l,T)whereT∈𝕊*). If u=w1, then G1≅∞1(p,q,l,Sr) and irrt(G)<irrt(G1)=(n-p-q-l+2)(n+p+q+l-1)+2p+2q+2l-8.
Ifu=w5, then G1≅∞5(p,q,l,Sr) and irrt(G)<irrt(G1)=(n-p-q-l+2)(n+p+q+l-1)+2p+2q+2l-8.
Ifu≠w1 and u≠w5, then we can get a new graph G2≅∞1(p,q,l,Sr) by β-transformation on G1; thus irrt(G)<irrt(G1)<irrt(G2)=(n-p-q-l+2)(n+p+q+l-1)+2p+2q+2l-8 by Lemma 6.
Subcase
1.2  (G1≅∞(p,q,l,T)whereT∈ℙ𝕊*). If u≠w1, let G2 be the graph obtained from G1 by β-transformation. Then, irrt(G1)<irrt(G2) by Lemma 5. Repeating α-transformation on G2 until we cannot get a new graph, the resulting graph is G3≅∞1(p,q,l,Sr). By Lemma 4, irrt(G2)<irrt(G3) and thus irrt(G)<irrt(G1)<irrt(G2)<irrt(G3)=(n-p-q-l+2)(n+p+q+l-1)+2p+2q+2l-8.
Ifu=w1 and dG1(u,v)=1, let G2 be the graph obtained from G1 by β-transformation; then G2≅∞1(p,q,l,Sr), and irrt(G)<irrt(G1)<irrt(G2)=(n-p-q-l+2)(n+p+q+l-1)+2p+2q+2l-8 by Lemma 5.
Ifu=w1 and dG1(u,v)>1, let G2 be the graph obtained from G1 by β-transformation and let G3 be the graph obtained from G2 by repeating α-transformation until we cannot get a new graph from G3 by α-transformation. Then by Lemmas 4 and 5, we know that G3≅∞1(p,q,l,Sr) and irrt(G)<irrt(G1)<irrt(G2)<irrt(G3)=(n-p-q-l+2)(n+p+q+l-1)+2p+2q+2l-8.
Case
2  (G≅∞(p,q,l,T)whereT∈𝕊*).The proof is similar to the proof of Subcase 1.1; thus, we omit it.
Case
3  (G≅∞(p,q,l,T)whereT∈ℙ𝕊*). The proof is similar to the proof of Subcase 1.2; thus, we omit it.
Combining the above arguments, we complete the proof.Theorem 12.
Letp,q,l,r be positive integers with p,q≥3 and l≥2. Then,(1)
Ifp≥4, then irrt(∞1(p,q,1,Sr))<irrt(∞1(p-1,q,1,Sr+1)).(2)
Ifq≥4, then irrt(∞1(p,q,1,Sr))<irrt(∞1(p,q-1,1,Sr+1)).(3)
Ifl≥3, then irrt(∞1(p,q,l,Sr))<irrt(∞1(p,q,l-1,Sr+1)).Proof.
Clearly, the proofs of(1), (2), and (3) are similar; we only show that (1) holds. Let n=p+q+l+r-3; then by formula (14), we have
(15)irrt(∞1(p-1,q,1,Sr+1))-irrt(∞1(p,q,1,Sr))=2p+2q+2l-6>0.Theorem 13.
Letn≥6 be a positive integer and let G∈Bn++ be a bicyclic graph on n vertices. Then, irrt(G)≤n2+n-34 and the equality holds if and only if G≅∞1(3,3,2,Sn-5) (see Figure 10).Figure 10
The graph∞1(3,3,2,Sn-5).Proof.
Letn,p,q,l,r be positive integers with p,q≥3, l≥2, and p+q+r+l-3=n and let G∈Bn++ be a bicyclic graph on n vertices obtained from ∞(p,q,l) with k(≥1) rooted trees T1,…,Tk attached. Then by Theorem 11, we have irrt(G)≤(n-p-q-l+2)(n+p+q+l-1)+2p+2q+2l-8, and the equality holds if and only if G≅∞1(p,q,l,Sr) or G≅∞5(p,q,l,Sr). Note that the results of Theorem 12 also hold for ∞5(p,q,l,Sr); then we only consider the case ∞1(p,q,l,Sr). Now we complete the proof by the following three cases.
Case
1  (p=q=3andl=2). Then, irrt(∞1(3,3,2,Sn-5))=n2+n-34.
Case
2  (p≥q≥3,l≥2, andp≥4). Then by (1), (2), and (3) of Theorem 12, we have irrt(∞1(p,q,l,Sr))<irrt(∞1(3,q,l,Sn-q-l))≤irrt(∞1(3,3,l,Sn-3-l))≤irrt(∞1(3,3,2,Sn-5)).
Case
3  (q≥p≥3,l≥2, andq≥4). The proof is similar to Case 2; thus, we omit it.


### 3.3. The Graph with the Maximal Total Irregularity inΘn

In this subsection, the bicyclic graph with the maximal total irregularity inΘn is determined.Letn,p,q,l,r be positive integers with l≥2, p,q≥l+1, and p+q+r-l-1=n; G=θ1(p,q,l,Sr). Clearly, the degree sequence of G is (r+2,3,2,…,2,1,…,1). By simple calculation,
(16)irrt(G)=(n-p-q+l)(n+p+q-l+1)+2p+2q-2l-4.Theorem 14.
Letn,p,q,l,r be positive integers with l≥2, p,q≥l+1, and p+q+r-l-1=n, and let G∈Θn be a bicyclic graph on n vertices obtained from θ(p,q,l) with k(≥1) rooted trees T1,…,Tk attached. Then, irrt(G)≤(n-p-q+l)(n+p+q-l+1)+2p+2q-2l-4, and the equality holds if and only if G≅θ1(p,q,l,Sr).Proof.
Ifr=1, then n=p+q-l, and the rooted trees T1,…,Tk are trivial; namely, |V(Ti)|=1 with i=1,…,k. Then, G=θ(p,q,l)=θ1(p,q,l,S1) and irrt(G)=(n-p-q+l)(n+p+q-l+1)+2p+2q-2l-4.
Ifr≥2, we complete the proof by the following three cases.
Case
1  (G≇θ(p,q,l,T)whereT∈𝕊*⋃‍ℙ𝕊*). Let G1 be the graph obtained from G by repeating α-transformation, and we cannot get a new graph from G1 by α-transformation. Then there exists a rooted tree T such that G1≅θ(p,q,l,T), where T∈𝕊*⋃‍ℙ𝕊* and irrt(G)<irrt(G1) by Lemma 4. Let u be the root of the rooted tree T.
Subcase
1.1  (G1≅θ(p,q,l,T)whereT∈𝕊*). If u=w1 or u=w5, then G1≅θ1(p,q,l,Sr) and irrt(G)<irrt(G1)=(n-p-q+l)(n+p+q-l+1)+2p+2q-2l-4.
Ifu≠w1 and u≠w5, then we can get a new graph G2≅θ1(p,q,l,Sr) by β-transformation on G1; thus irrt(G)<irrt(G1)<irrt(G2)=(n-p-q+l)(n+p+q-l+1)+2p+2q-2l-4 by Lemma 6.
Subcase
1.2  (G1≅θ(p,q,l,T)whereT∈ℙ𝕊*). If u≠w1, let G2 be the graph obtained from G1 by β-transformation. Then, irrt(G1)<irrt(G2) by Lemma 5. Repeating α-transformation on G2 until we cannot get a new graph, the resulting graph is G3≅θ1(p,q,l,Sr). By Lemma 4, irrt(G2)<irrt(G3) and thus irrt(G)<irrt(G1)<irrt(G2)<irrt(G3)=(n-p-q+l)(n+p+q-l+1)+2p+2q-2l-4.
Ifu=w1 and dG1(u,v)=1, let G2 be the graph obtained from G1 by β-transformation; then G2≅θ1(p,q,l,Sr) and irrt(G)<irrt(G1)<irrt(G2)=(n-p-q+l)(n+p+q-l+1)+2p+2q-2l-4 by Lemma 5.
Ifu=w1 and dG1(u,v)>1, let G2 be the graph obtained from G1 by β-transformation and let G3 be the graph obtained from G2 by repeating α-transformation until we cannot get a new graph from G3 by α-transformation. Then by Lemmas 4 and 5, we know that G3≅θ1(p,q,l,Sr) and irrt(G)<irrt(G1)<irrt(G2)<irrt(G3)=(n-p-q+l)(n+p+q-l+1)+2p+2q-2l-4.
Case
2  (G≅θ(p,q,l,T)whereT∈𝕊*). The proof is similar to the proof of Subcase 1.1; thus, we omit it.
Case
3  (G≅θ(p,q,l,T)whereT∈ℙ𝕊*). The proof is similar to the proof of Subcase 1.2; thus, we omit it.
Combining the above arguments, we complete the proof.Theorem 15.
Letp,q,l,r be positive integers with l≥2 and p,q≥l+1. Then,(1)
Ifp≥4, then irrt(θ1(p,q,1,Sr))<irrt(θ1(p-1,q,1,Sr+1)).(2)
Ifq≥4, then irrt(θ1(p,q,1,Sr))<irrt(θ1(p,q-1,1,Sr+1)).(3)
Ifl≥3, then irrt(θ1(p,q,l,Sr))<irrt(θ1(p-1,q-1,l-1,Sr+1)).Proof.
Clearly, the proofs of(1), (2), and (3) are similar; we only show that (1) holds. Let n=p+q+l+r-3; then by formula (14), we have
(17)irrt(θ1(p-1,q,1,Sr+1))-irrt(θ1(p,q,1,Sr))=2p+2q-2l-2>0.Theorem 16.
Letn≥4 be a positive integer and let G∈Θn be a bicyclic graph on n vertices. Then, irrt(G)≤n2+n-16 and the equality holds if and only if G≅θ1(3,3,2,Sn-3) (see Figure 11).Figure 11
The graphθ1(3,3,2,Sn-3).Proof.
Letn,p,q,l,r be positive integers with l≥2, p,q≥l+1, and p+q+r-l-1=n and let G∈Θn be a bicyclic graph on n vertices obtained from θ(p,q,l) with k(≥1) rooted trees T1,…,Tk attached. Then by Theorem 14, we have irrt(G)≤(n-p-q+l)(n+p+q-l+1)+2p+2q-2l-4, and the equality holds if and only if G≅θ1(p,q,l,Sr). Now we complete the proof by the following three cases.
Case
1  (p=q=3andl=2). Then, irrt(θ1(3,3,2,Sn-3))=n2+n-16.
Case
2 (
p
≥
q
≥
l
+
1
,
l
≥
2
except for
p
=
q
=
l
+
1
=
3
).
Subcase
2.1  (p>l+1,l=2). Then by (1) and (2) of Theorem 15, we have irrt(θ1(p,q,2,Sr))<irrt(θ1(3,q,2,Sp+r-3))≤irrt(θ1(3,3,2,Sn-3)).
Subcase
2.2  (p≥l+1,l≥3). Then by (3), (1), and (2) of Theorem 15, we have irrt(θ1(p,q,l,Sr))<irrt(θ1(p-l+2,q-l+2,2,Sr+l-2))≤irrt(θ1(3,q-l+2,2,Sp+r-3))≤irrt(θ1(3,3,2,Sn-3)).
Case
3 (
q
≥
p
≥
l
+
1
,
l
≥
2
except for
p
=
q
=
l
+
1
=
3
).
The proof is similar to Case 2; thus, we omit it.


### 3.4. Bicyclic Graphs with the Maximal Total Irregularity

Byℬn=Bn+∪Bn++∪Θn and Theorems 10, 13, and 16, the following result is obvious.Theorem 17.
Letn≥4 be a positive integer and let G∈ℬn be a bicyclic graph on n vertices. Then, irrt(G)≤n2+n-16 and the equality holds if and only if G≅θ1(3,3,2,Sn-3) (see Figure 11).


## 3.1. The Graph with the Maximal Total Irregularity inBn+

In this subsection, the bicyclic graph with the maximal total irregularity inBn+ is determined.Letn,p,q,r be positive integers with p,q≥3 and p+q+r-2=n; G=∞1(p,q,1,Sr). Clearly, the degree sequence of G is (r+3,2,…,2,1,…,1). By simple calculation, we have
(13)irrt(G)=(n-p-q+1)(n+p+q)+2p+2q-4.Theorem 8.
Letn,p,q,r be positive integers with p,q≥3 and p+q+r-2=n and let G∈Bn+ be a bicyclic graph on n vertices obtained from ∞(p,q,1) with k(≥1) rooted trees T1,…,Tk attached. Then, irrt(G)≤(n-p-q+1)(n+p+q)+2p+2q-4, and the equality holds if and only if G≅∞1(p,q,1,Sr).Proof.
Ifr=1, then n=p+q-1, and the rooted trees T1,…,Tk are trivial; namely, |V(Ti)|=1 with i=1,…,k. Then, G=∞(p,q,1)=∞1(p,q,1,S1) and irrt(G)=(n-p-q+1)(n+p+q)+2p+2q-4.
Ifr≥2, we complete the proof by the following three cases.
Case
1  (G≇∞(p,q,1,T)whereT∈𝕊*⋃‍ℙ𝕊*). Let G1 be the graph obtained from G by repeating α-transformation, and we cannot get a new graph from G1 by α-transformation. Then there exists a rooted tree T such that G1≅∞(p,q,1,T) where T∈𝕊*⋃‍ℙ𝕊* and irrt(G)<irrt(G1) by Lemma 4. Let u be the root of the rooted tree T.
Subcase
1.1  (G1≅∞(p,q,1,T)whereT∈𝕊*). If u=w1, then G1≅∞1(p,q,1,Sr) and irrt(G)<irrt(G1)=(n-p-q+1)(n+p+q)+2p+2q-4.
Ifu≠w1, then we can get a new graph G2≅∞1(p,q,1,Sr) by β-transformation on G1; thus irrt(G)<irrt(G1)<irrt(G2)=(n-p-q+1)(n+p+q)+2p+2q-4 by Lemma 6.
Subcase
1.2  (G1≅∞(p,q,1,T)whereT∈ℙ𝕊*). If u≠w1, let G2 be the graph obtained from G1 by β-transformation. Then irrt(G1)<irrt(G2) by Lemma 5. Repeating α-transformation on G2 until we cannot get a new graph, the resulting graph is G3≅∞1(p,q,1,Sr). By Lemma 4, irrt(G2)<irrt(G3) and thus irrt(G)<irrt(G1)<irrt(G2)<irrt(G3)=(n-p-q+1)(n+p+q)+2p+2q-4.
Ifu=w1 and dG1(u,v)=1, let G2 be the graph obtained from G1 by β-transformation; then G2≅∞1(p,q,1,Sr) and irrt(G)<irrt(G1)<irrt(G2)=(n-p-q+1)(n+p+q)+2p+2q-4 by Lemma 5.
Ifu=w1 and dG1(u,v)>1, Let G2 be the graph obtained from G1 by β-transformation and let G3 be the graph obtained from G2 by repeating α-transformation until we cannot get a new graph from G3 by α-transformation. Then by Lemmas 4 and 5, we know that G3≅∞1(p,q,1,Sr) and irrt(G)<irrt(G1)<irrt(G2)<irrt(G3)=(n-p-q+1)(n+p+q)+2p+2q-4.
Case
2  (G≅∞(p,q,1,T)whereT∈𝕊*).
The proof is similar to the proof of Subcase 1.1; thus, we omit it.
Case
3   (G≅∞(p,q,1,T)whereT∈ℙ𝕊*).
The proof is similar to the proof of Subcase 1.2; thus, we omit it.
Combining the above arguments, we complete the proof.Theorem 9.
Letp,q,r be positive integers with p,q≥3.(1)
Ifp≥4, then irrt(∞1(p,q,1,Sr))<irrt(∞1(p-1,q,1,Sr+1)).(2)
Ifq≥4, then irrt(∞1(p,q,1,Sr))<irrt(∞1(p,q-1,1,Sr+1)).Proof.
Clearly, the proofs of(1) and (2) are similar; we only show that (1) holds. Let n=p+q+r-2; by formula (13), we have irrt(∞1(p-1,q,1,Sr+1))-irrt(∞1(p,q,1,Sr))=2p+2q-4>0.Theorem 10.
Letn≥5 be a positive integer, and let G∈Bn+ be a bicyclic graph on n vertices. Then irrt(G)≤n2+n-22 and the equality holds if and only if G≅∞1(3,3,1,Sn-4) (see Figure 9).Figure 9
The graph∞1(3,3,1,Sn-4).Proof.
Letn,p,q,r be positive integers with p,q≥3 and p+q+r-2=n and let G∈Bn+ be a bicyclic graph on n vertices obtained from ∞(p,q,1) with k(≥1) rooted trees T1,…,Tk attached. Then by Theorem 8, we have irrt(G)≤(n-p-q+1)(n+p+q)+2p+2q-4, and the equality holds if and only if G≅∞1(p,q,1,Sr). Now we complete the proof by the following three cases.
Case
1  (p=q=3). Then, irrt(∞1(3,3,1,Sn-4))=n2+n-22.
Case
2  (p≥q≥3andp≥4). Then by using Theorem 9  p+q-6 times, we have irrt(∞1(p,q,1,Sr))<irrt(∞1(3,q,1,Sn-q-1))≤irrt(∞1(3,3,1,Sn-4)).
Case
3  (q≥p≥3andq≥4). The proof is similar to Case 2; thus, we omit it.


## 3.2. The Graph with the Maximal Total Irregularity inBn++

In this subsection, the bicyclic graph with the maximal total irregularity inBn++ is determined.Letn,p,q,r,l be positive integers with p,q≥3, l≥2, and p+q+r+l-3=n; G=∞1(p,q,1,Sr) or G=∞5(p,q,l,Sr). Clearly, the degree sequence of G is (r+2,3,2,…,2,1,…,1). By simple calculation, we have
(14)irrt(G)=(n-p-q-l+2)(n+p+q+l-1)+2p+2q+2l-8.Theorem 11.
Letn,p,q,l,r be positive integers with p,q≥3, l≥2, and p+q+r+l-3=n and let G∈Bn++ be a bicyclic graph on n vertices obtained from ∞(p,q,l) with k(≥1) rooted trees T1,…,Tk attached. Then, irrt(G)≤(n-p-q-l+2)(n+p+q+l-1)+2p+2q+2l-8, and the equality holds if and only if G≅∞1(p,q,l,Sr) or G≅∞5(p,q,l,Sr).Proof.
Ifr=1, then n=p+q+l-2, and the rooted trees T1,…,Tk are trivial; namely, |V(Ti)|=1 with i=1,…,k. Then, G=∞(p,q,l)=∞1(p,q,l,S1) and irrt(G)=(n-p-q-l+2)(n+p+q+l-1)+2p+2q+2l-8.
Ifr≥2, we complete the proof by the following three cases.
Case
1  (G≇∞(p,q,l,T)whereT∈𝕊*⋃‍ℙ𝕊*). Let G1 be the graph obtained from G by repeating α-transformation, and we cannot get a new graph from G1 by α-transformation. Then there exists a rooted tree T such that G1≅∞(p,q,l,T), where T∈𝕊*⋃‍ℙ𝕊* and irrt(G)<irrt(G1) by Lemma 4. Let u be the root of the rooted tree T.
Subcase
1.1  (G1≅∞(p,q,l,T)whereT∈𝕊*). If u=w1, then G1≅∞1(p,q,l,Sr) and irrt(G)<irrt(G1)=(n-p-q-l+2)(n+p+q+l-1)+2p+2q+2l-8.
Ifu=w5, then G1≅∞5(p,q,l,Sr) and irrt(G)<irrt(G1)=(n-p-q-l+2)(n+p+q+l-1)+2p+2q+2l-8.
Ifu≠w1 and u≠w5, then we can get a new graph G2≅∞1(p,q,l,Sr) by β-transformation on G1; thus irrt(G)<irrt(G1)<irrt(G2)=(n-p-q-l+2)(n+p+q+l-1)+2p+2q+2l-8 by Lemma 6.
Subcase
1.2  (G1≅∞(p,q,l,T)whereT∈ℙ𝕊*). If u≠w1, let G2 be the graph obtained from G1 by β-transformation. Then, irrt(G1)<irrt(G2) by Lemma 5. Repeating α-transformation on G2 until we cannot get a new graph, the resulting graph is G3≅∞1(p,q,l,Sr). By Lemma 4, irrt(G2)<irrt(G3) and thus irrt(G)<irrt(G1)<irrt(G2)<irrt(G3)=(n-p-q-l+2)(n+p+q+l-1)+2p+2q+2l-8.
Ifu=w1 and dG1(u,v)=1, let G2 be the graph obtained from G1 by β-transformation; then G2≅∞1(p,q,l,Sr), and irrt(G)<irrt(G1)<irrt(G2)=(n-p-q-l+2)(n+p+q+l-1)+2p+2q+2l-8 by Lemma 5.
Ifu=w1 and dG1(u,v)>1, let G2 be the graph obtained from G1 by β-transformation and let G3 be the graph obtained from G2 by repeating α-transformation until we cannot get a new graph from G3 by α-transformation. Then by Lemmas 4 and 5, we know that G3≅∞1(p,q,l,Sr) and irrt(G)<irrt(G1)<irrt(G2)<irrt(G3)=(n-p-q-l+2)(n+p+q+l-1)+2p+2q+2l-8.
Case
2  (G≅∞(p,q,l,T)whereT∈𝕊*).The proof is similar to the proof of Subcase 1.1; thus, we omit it.
Case
3  (G≅∞(p,q,l,T)whereT∈ℙ𝕊*). The proof is similar to the proof of Subcase 1.2; thus, we omit it.
Combining the above arguments, we complete the proof.Theorem 12.
Letp,q,l,r be positive integers with p,q≥3 and l≥2. Then,(1)
Ifp≥4, then irrt(∞1(p,q,1,Sr))<irrt(∞1(p-1,q,1,Sr+1)).(2)
Ifq≥4, then irrt(∞1(p,q,1,Sr))<irrt(∞1(p,q-1,1,Sr+1)).(3)
Ifl≥3, then irrt(∞1(p,q,l,Sr))<irrt(∞1(p,q,l-1,Sr+1)).Proof.
Clearly, the proofs of(1), (2), and (3) are similar; we only show that (1) holds. Let n=p+q+l+r-3; then by formula (14), we have
(15)irrt(∞1(p-1,q,1,Sr+1))-irrt(∞1(p,q,1,Sr))=2p+2q+2l-6>0.Theorem 13.
Letn≥6 be a positive integer and let G∈Bn++ be a bicyclic graph on n vertices. Then, irrt(G)≤n2+n-34 and the equality holds if and only if G≅∞1(3,3,2,Sn-5) (see Figure 10).Figure 10
The graph∞1(3,3,2,Sn-5).Proof.
Letn,p,q,l,r be positive integers with p,q≥3, l≥2, and p+q+r+l-3=n and let G∈Bn++ be a bicyclic graph on n vertices obtained from ∞(p,q,l) with k(≥1) rooted trees T1,…,Tk attached. Then by Theorem 11, we have irrt(G)≤(n-p-q-l+2)(n+p+q+l-1)+2p+2q+2l-8, and the equality holds if and only if G≅∞1(p,q,l,Sr) or G≅∞5(p,q,l,Sr). Note that the results of Theorem 12 also hold for ∞5(p,q,l,Sr); then we only consider the case ∞1(p,q,l,Sr). Now we complete the proof by the following three cases.
Case
1  (p=q=3andl=2). Then, irrt(∞1(3,3,2,Sn-5))=n2+n-34.
Case
2  (p≥q≥3,l≥2, andp≥4). Then by (1), (2), and (3) of Theorem 12, we have irrt(∞1(p,q,l,Sr))<irrt(∞1(3,q,l,Sn-q-l))≤irrt(∞1(3,3,l,Sn-3-l))≤irrt(∞1(3,3,2,Sn-5)).
Case
3  (q≥p≥3,l≥2, andq≥4). The proof is similar to Case 2; thus, we omit it.


## 3.3. The Graph with the Maximal Total Irregularity inΘn

In this subsection, the bicyclic graph with the maximal total irregularity inΘn is determined.Letn,p,q,l,r be positive integers with l≥2, p,q≥l+1, and p+q+r-l-1=n; G=θ1(p,q,l,Sr). Clearly, the degree sequence of G is (r+2,3,2,…,2,1,…,1). By simple calculation,
(16)irrt(G)=(n-p-q+l)(n+p+q-l+1)+2p+2q-2l-4.Theorem 14.
Letn,p,q,l,r be positive integers with l≥2, p,q≥l+1, and p+q+r-l-1=n, and let G∈Θn be a bicyclic graph on n vertices obtained from θ(p,q,l) with k(≥1) rooted trees T1,…,Tk attached. Then, irrt(G)≤(n-p-q+l)(n+p+q-l+1)+2p+2q-2l-4, and the equality holds if and only if G≅θ1(p,q,l,Sr).Proof.
Ifr=1, then n=p+q-l, and the rooted trees T1,…,Tk are trivial; namely, |V(Ti)|=1 with i=1,…,k. Then, G=θ(p,q,l)=θ1(p,q,l,S1) and irrt(G)=(n-p-q+l)(n+p+q-l+1)+2p+2q-2l-4.
Ifr≥2, we complete the proof by the following three cases.
Case
1  (G≇θ(p,q,l,T)whereT∈𝕊*⋃‍ℙ𝕊*). Let G1 be the graph obtained from G by repeating α-transformation, and we cannot get a new graph from G1 by α-transformation. Then there exists a rooted tree T such that G1≅θ(p,q,l,T), where T∈𝕊*⋃‍ℙ𝕊* and irrt(G)<irrt(G1) by Lemma 4. Let u be the root of the rooted tree T.
Subcase
1.1  (G1≅θ(p,q,l,T)whereT∈𝕊*). If u=w1 or u=w5, then G1≅θ1(p,q,l,Sr) and irrt(G)<irrt(G1)=(n-p-q+l)(n+p+q-l+1)+2p+2q-2l-4.
Ifu≠w1 and u≠w5, then we can get a new graph G2≅θ1(p,q,l,Sr) by β-transformation on G1; thus irrt(G)<irrt(G1)<irrt(G2)=(n-p-q+l)(n+p+q-l+1)+2p+2q-2l-4 by Lemma 6.
Subcase
1.2  (G1≅θ(p,q,l,T)whereT∈ℙ𝕊*). If u≠w1, let G2 be the graph obtained from G1 by β-transformation. Then, irrt(G1)<irrt(G2) by Lemma 5. Repeating α-transformation on G2 until we cannot get a new graph, the resulting graph is G3≅θ1(p,q,l,Sr). By Lemma 4, irrt(G2)<irrt(G3) and thus irrt(G)<irrt(G1)<irrt(G2)<irrt(G3)=(n-p-q+l)(n+p+q-l+1)+2p+2q-2l-4.
Ifu=w1 and dG1(u,v)=1, let G2 be the graph obtained from G1 by β-transformation; then G2≅θ1(p,q,l,Sr) and irrt(G)<irrt(G1)<irrt(G2)=(n-p-q+l)(n+p+q-l+1)+2p+2q-2l-4 by Lemma 5.
Ifu=w1 and dG1(u,v)>1, let G2 be the graph obtained from G1 by β-transformation and let G3 be the graph obtained from G2 by repeating α-transformation until we cannot get a new graph from G3 by α-transformation. Then by Lemmas 4 and 5, we know that G3≅θ1(p,q,l,Sr) and irrt(G)<irrt(G1)<irrt(G2)<irrt(G3)=(n-p-q+l)(n+p+q-l+1)+2p+2q-2l-4.
Case
2  (G≅θ(p,q,l,T)whereT∈𝕊*). The proof is similar to the proof of Subcase 1.1; thus, we omit it.
Case
3  (G≅θ(p,q,l,T)whereT∈ℙ𝕊*). The proof is similar to the proof of Subcase 1.2; thus, we omit it.
Combining the above arguments, we complete the proof.Theorem 15.
Letp,q,l,r be positive integers with l≥2 and p,q≥l+1. Then,(1)
Ifp≥4, then irrt(θ1(p,q,1,Sr))<irrt(θ1(p-1,q,1,Sr+1)).(2)
Ifq≥4, then irrt(θ1(p,q,1,Sr))<irrt(θ1(p,q-1,1,Sr+1)).(3)
Ifl≥3, then irrt(θ1(p,q,l,Sr))<irrt(θ1(p-1,q-1,l-1,Sr+1)).Proof.
Clearly, the proofs of(1), (2), and (3) are similar; we only show that (1) holds. Let n=p+q+l+r-3; then by formula (14), we have
(17)irrt(θ1(p-1,q,1,Sr+1))-irrt(θ1(p,q,1,Sr))=2p+2q-2l-2>0.Theorem 16.
Letn≥4 be a positive integer and let G∈Θn be a bicyclic graph on n vertices. Then, irrt(G)≤n2+n-16 and the equality holds if and only if G≅θ1(3,3,2,Sn-3) (see Figure 11).Figure 11
The graphθ1(3,3,2,Sn-3).Proof.
Letn,p,q,l,r be positive integers with l≥2, p,q≥l+1, and p+q+r-l-1=n and let G∈Θn be a bicyclic graph on n vertices obtained from θ(p,q,l) with k(≥1) rooted trees T1,…,Tk attached. Then by Theorem 14, we have irrt(G)≤(n-p-q+l)(n+p+q-l+1)+2p+2q-2l-4, and the equality holds if and only if G≅θ1(p,q,l,Sr). Now we complete the proof by the following three cases.
Case
1  (p=q=3andl=2). Then, irrt(θ1(3,3,2,Sn-3))=n2+n-16.
Case
2 (
p
≥
q
≥
l
+
1
,
l
≥
2
except for
p
=
q
=
l
+
1
=
3
).
Subcase
2.1  (p>l+1,l=2). Then by (1) and (2) of Theorem 15, we have irrt(θ1(p,q,2,Sr))<irrt(θ1(3,q,2,Sp+r-3))≤irrt(θ1(3,3,2,Sn-3)).
Subcase
2.2  (p≥l+1,l≥3). Then by (3), (1), and (2) of Theorem 15, we have irrt(θ1(p,q,l,Sr))<irrt(θ1(p-l+2,q-l+2,2,Sr+l-2))≤irrt(θ1(3,q-l+2,2,Sp+r-3))≤irrt(θ1(3,3,2,Sn-3)).
Case
3 (
q
≥
p
≥
l
+
1
,
l
≥
2
except for
p
=
q
=
l
+
1
=
3
).
The proof is similar to Case 2; thus, we omit it.


## 3.4. Bicyclic Graphs with the Maximal Total Irregularity

Byℬn=Bn+∪Bn++∪Θn and Theorems 10, 13, and 16, the following result is obvious.Theorem 17.
Letn≥4 be a positive integer and let G∈ℬn be a bicyclic graph on n vertices. Then, irrt(G)≤n2+n-16 and the equality holds if and only if G≅θ1(3,3,2,Sn-3) (see Figure 11).



---

*Source: 785084-2014-04-10.xml*