Printer Friendly

The irregularity of two types of trees.

The irregularity of a graph G is defined as the sum of weights |d(u) - d(v)| of all edges uv of G, where d(u) and d(v) are the degrees of the vertices u and v in G, respectively. In this paper, some structural properties on trees with maximum (or minimum) irregularity among trees with given degree sequence and trees with given branching number are explored, respectively. Moreover, the corresponding trees with maximum (or minimum) irregularity are also found, respectively.

Keywords: Irregularity, trees, degree sequence, branching number.

1 Introduction

Let G be a simple connected graph with vertex set V(G) and edge set E(G). Its order is | V(G) |, denoted by n, and its size is |E(G)|, denoted by m. For v [member of] V(G), let [N.sub.G](v) (or N(v) for short) be the set of neighbors of v in G, and [d.sub.G](v) = |[N.sub.G](v)| (or d(v) for short) be the degree of v in G. A pendent vertex of G is a vertex of degree 1. Let [[DELTA].sub.1](G), [[DELTA].sub.2](G) and [delta](G) (or [[DELTA].sub.1], [[DELTA].sub.2] and [delta] for short) be the largest, second largest and minimum degrees of G, respectively.

A graph whose all vertices have equal degrees is said to be regular, otherwise it is irregular. Albertson [3] defined the imbalance of an edge uv [member of] E(G) as |d(u) - d(v)| and the irregularity of G as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

where the summation is over all (unordered) edges uv in G.

The problem of determining the graph with maximum (or minimum) irregularity (or estimating bounds on irr(G)) among some classes of graphs is of great interest. Hansen and Melot [6] determined the maximum value for the irregularity of graphs of order n with m edges and constructed the corresponding graph which attaining this value; Henning and Rautenbach [7] explored the structural properties on bipartite graphs with maximum irregularity. Various upper bounds on the irregularity of some classes of graphs, such as [K.sub.r+1]-free graphs, bipartite graphs, triangle-free graphs were deduced in [14, 3, 1], respectively. In particular, Zhou [14] established the relationship between irr(G) and [Z.sub.1] (G), and respectively determined the graphs with maximum irregularity among trees and unicyclic graphs with a given number of pendent vertices, where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the first Zagreb index of G. Recently, Luo and Zhou [9] determined the graphs with maximum irregularity among trees and unicyclic graphs with given matching number, respectively. More results on imbalance, the irregularity of a graph can be found in [5, 10, 2, 11].

A positive integer sequence [pi] = {[d.sub.1], [d.sub.2],... , [d.sub.n]} is called the degree sequence of G if [d.sub.i] = d([v.sub.i]) for vi [member of] V(G), i = 1,... , n. Throughout this paper, we order the vertex degrees in non-increasing order, i.e., [d.sub.1] [greater than or equal to] [d.sub.2] [greater than or equal to]... [greater than or equal to] [d.sub.n]. Also, a sequence [pi] = {[d.sub.1], [d.sub.2],... ,[d.sub.n]} is called a tree degree sequence if there exists a tree T having [pi] as its degree sequence. Furthermore, the sequence [pi] = {[d.sub.1], [d.sub.2],... , [d.sub.n]} is a degree sequence of a tree of order n if and only if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [4]. For a tree T, a vertex of degree 1 is also called a leaf (or a pendent vertex); a vertex v with d(v) [greater than or equal to] 3 is called a branching vertex. The branching number of T, denoted by k(T), is the number of those vertices v [member of] V(T) with d(v) [greater than or equal to] 3. For convenience, the degree sequence of T ([pi] (T)) is the sequence of the degrees (in descending order) of non-leaf vertices. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the sets of trees of order n with degree sequence [pi] and k branching vertices, respectively. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) be the tree which has maximum (or minimum) irregularity among trees in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) be the tree which has maximum (or minimum) irregularity among all trees in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In the present paper, we explore some properties on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]), and find the corresponding trees [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]), as well as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]).

2 Preliminaries

We use G - uv to denote the graph obtained by deleting the edge uv [member of] E(G) from G. Similarly, G + uv is the graph obtained by adding an edge uv [??] E(G) to G.

[FIGURE 1 OMITTED]

Consider a path [v.sub.0][v.sub.1][v.sub.2]... [v.sub.t][v.sub.t+1] in a tree T, where [d.sub.T]([v.sub.0]) = [d.sub.T]([v.sub.t+1]) = 1, let [T.sup.0] be a new tree obtained from T by reversing the order of the components attached to [v.sub.i], [v.sub.i+1],... ,[v.sub.k]. That is [T.sub.0] = T - [v.sub.i-1] [v.sub.i] -[v.sub.k][v.sub.k+1]+ [v.sub.i-1][v.sub.k] + [v.sub.i][v.sub.k+1]. Clearly, [T.sup.0] and T have the same degree sequence. This operation is denoted by S([v.sub.i], [v.sub.k]) on the path [v.sub.0][v.sub.1][v.sub.2]... [v.sub.t][v.sub.t+1]. The process of this operation is shown in Fig. 1.

Let e = uv be an edge of a graph G. Let G' be the graph obtained from G by contracting the edge e into a new vertex u! and adding a new pendent edge u'v', where v' is a new pendent vertex. We say that G' is obtained from G by separating an edge uv (shown in Fig. 2).

[FIGURE 2 OMITTED]

Lemma 2.1 ([8]) For e = uv [member of] E(G), let G' be the graph obtained from G by separating an edge uv. If dG(u) [greater than or equal to] [d.sub.G](v) for any v [member of] [N.sub.G](u), then we have irr(G') > irr(G).

Lemma 2.2 For positive integer x [less than or equal to] [[n-2]/2], the function f(n, x) = [n.sup.2] + (1 - 4x)n + 4[x.sup.2] - 2 is monotonically decreasing on x.

Proof: Consider the derivative on x of the function f(n, x). Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then f(n, x) is monotonically decreasing on x [less than or equal to] [[n-2]/2]. This completes the proof. []

3 Maximal (or minimal) irregularity of graphs in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In this section, we explore some properties on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]), and find the corresponding trees [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]).

3.1 Properties on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Lemma 3.1 Each path [v.sub.0][v.sub.1]... [v.sub.t][v.sub.t+1] with d([v.sub.0]) = d([v.sub.t+1]) = 1 in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], has the following properties:

1. if i is odd, then d(vi) [greater than or equal to] d([v.sub.t+1-i]) [greater than or equal to] d([v.sub.k])for i [less than or equal to] k [less than or equal to] t + 1 - i;

2. if i is even, then d([v.sub.i]) [less than or equal to] d([v.sub.t+1-i]) [less than or equal to] d([v.sub.k])for i [less than or equal to] k [less than or equal to] t + 1 - i.

Proof: We prove the result by induction on i. For i = 1, we will prove that d([v.sub.1]) [greater than or equal to] d([v.sub.t]) > d([v.sub.k]) for 2 [less than or equal to] k [less than or equal to] t - 1. Suppose the opposite that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ([v.sub.k]) for some 2 [less than or equal to] k [less than or equal to] t - 1. Let [T.sup.0] be a tree by applying S([v.sub.1],[v.sub.k]) to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Clearly, [T.sup.0] [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that the edges [v.sub.0][v.sub.1] and [v.sub.k][v.sub.k]+1 in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are transformed to the edges [v.sub.0][v.sub.k] and [v.sub.1][v.sub.k]+1 in [T.sup.0], respectively. Hence we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This is a contradiction. Hence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. At the same time, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Similarly, we can prove that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for 2 [less than or equal to] k [less than or equal to] t - 1. Hence, we conclude that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for 1 [less than or equal to] k [less than or equal to]t.

Now, assume that the result holds for other values. If i [greater than or equal to] 2 is even, assume that the result holds for any l [less than or equal to] i - 1. From that, if l = i - 1 is odd, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for i [less than or equal to] k [less than or equal to] t + 2 - i and i = 1, 2,... , |(t + 1)/2]. If l = i is even, we should prove that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for (i [less than or equal to] k [less than or equal to] t + 1 - i and i = 1, 2,... , [(t + 1)/2]). Suppose the opposite that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some i + 1[less than or equal to]k[less than or equal to]t+1 - i. Let [T.sup.0] be a tree by applying S([v.sub.i], [v.sub.k]) to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Clearly, [T.sup.0] [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that [v.sub.i-1][v.sub.i] and [v.sub.k][v.sub.k]+1 in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are transformed to [v.sub.i-1][v.sub.k] and [v.sub.i][v.sub.k+1] in [T.sup.0], respectively. By the inductive hypothesis, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

a contradiction. Hence, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any i+1 [less than or equal to] k [less than or equal to] t+1 - i. At the same time, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Now we prove that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for i + 1 [less than or equal to] k [less than or equal to] t+1 - i. Suppose the opposite that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for i + 1 [less than or equal to] k [less than or equal to] t + 1 - i. Let [T.sup.0] be the tree obtained by applying S([v.sub.k], [v.sub.t+1-i]) to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Clearly, [T.sup.0] [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that [v.sub.k-1][v.sub.k] and [v.sub.t+1-i][v.sub.t+2-i] in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are transformed to [v.sub.k-1][v.sub.t+1-i] and [v.sub.k][v.sub.t+2-i] in [T.sup.0], respectively. Moreover, by the inductive hypothesis, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

a contradiction. Hence we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for i + 1 [less than or equal to] k [less than or equal to] t + 1 - i. Therefore, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for i [less than or equal to] k [less than or equal to]t + 1- i and i = 1, 2,... , |(t + 1)/2].

The case for odd i is similar. The proof is completed. []

Let [v.sub.i,j] be the vertex whose closest leaf is at distance i, and let [v.sub.0,j] be a leaf in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For integers i, j, k, l, by Lemma 3.1, we have the following:

Lemma 3.2 For 1 [less than or equal to] i < j, we have

1. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for odd i;

2. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for even i.

For a tree T, let [P.sub.T] be the set of leaves in T, and [[??].sub.T] be the set of vertices that adjacent to the leaves in T. Let d' = min{d(v), v [member of] [[??].sub.T]} and [P.sub.T] be the set of leaves whose adjacent vertices have degree d' in T.

Lemma 3.3 For trees T and T* with root r *, let T' and T" be two trees obtained from T by identifying the root [r.sup.#] of [T.sup.#] with v' and v", respectively, where v' [member of] [P.sub.T] and v" [member of] [P.sub.T] \ [P.sub.T]. Then irr(T') > irr(T").

Proof: Let[v.sub.1],[v.sub.2] [member of] V(T) such that [v.sub.1]v' [member of] E(T) and [v.sub.2]v" [member of] E(T). Note that [d.sub.T] ([v.sub.1]) = d' < [d.sub.T]([v.sub.2]). Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This completes the proof. []

The following recursive algorithm can be used to construct the tree [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with [pi] = {d1, d2,... , [d.sub.m]}.

(1) If m - 1 [less than or equal to] [d.sub.m], then by Lemma 3.1, it is easy to get a tree [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]:

Rooted at r with [d.sub.m] children with degrees [d.sub.1],... , [d.sub.m-1] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII];

(2) If m - 1 [greater than or equal to] [d.sub.m] + 1, then by Lemma 3.2, we see that the vertices in {[v.sub.1,j]|j = 1, 2,...} take the largest degrees and they are adjacent to the vertices (in {[v.sub.2,k]|k = 1,2,...}) with the smallest degrees. Construct the subtrees that contain vertices in {[v.sub.0,i]|i = 1,2,... }, {[v.sub.1,j]|j = 1,2,... } and {[v.sub.2,k]|k = 1, 2,... } first. Note that by Lemma 3.1, we will let the larger degree vertex be adjacent to the smaller degree vertex whenever possible. Thus, we produce the following subtree [T.sub.1]:

Rooted at r with [d.sub.m] - 1 children with degrees [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where r [member of] {[v.sub.2,k]|k = 1,2,...} with degree [d.sub.m] in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the children of r are vertices in {[v.sub.1,j] |j = 1,2,...}.

Note that removing T1 (except the root) from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] results in a new tree S with degree sequence {[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]}, in which Lemmas 3.1 and 3.2 still hold. Thus S is a tree with the new degree sequence has the maximum irregularity.

(3) Now the only problem is how to attach [T.sub.1] to S (by identifying the root of [T.sub.1] with a leaf of S). By Lemma 3.3, we should identify the root of [T.sub.1] with a vertex v in [P.sub.T] of S.

We now give an example which is a tree [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with degree sequence [pi] = {7,6,5, 5,4,4,3,3, 3, 2} to illustrate above mentioned process.

Firstly, by (2) we have the subtree [T.sub.1] and new degree sequence{6, 5, 5,4,4, 3, 3, 3}. Then, we can find a tree with this new degree sequence has the maximum irregularity. Similarly, we also have the subtree [T.sub.2] and [T.sub.3] by (2). The remaining degree sequence {4, 3} satisfies (1), producing the tree S with maximum irregularity, where [T.sub.1], [T.sub.2],[T.sub.3] and S are shown in Fig. 3;

Secondly, attaching T3 to S (according to (3)) yields a tree with degree sequence{5, 4, 4, 3, 3} has maximum irregularity. Now attaching [T.sub.2] to this new tree (according to (3)) yields a tree with degree sequence {6, 5, 5,4, 4, 3, 3, 3} has the maximum irregularity. We then have a new S (see Fig. 4);

Lastly, finding a leaf in the new S (Fig. 4) whose neighbor has the smallest degree, attaching [T.sub.1] to the new S as described above in (3) yields [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. However, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is not necessarily unique, two of them are shown in Fig. 5, both are achieved through our algorithm.

[FIGURE 3 OMITTED]

[FIGURE 4 OMITTED]

[FIGURE 5 OMITTED]

3.2 Properties on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Lemma 3.4 Each path [v.sub.0][v.sub.1][v.sub.2]... [v.sub.t][v.sub.t+1] with d([v.sub.0]) = d([v.sub.t+1]) = 1 in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], has the following properties:

d([v.sub.i]) [less than or equal to] d([v.sub.t+1-i]) [less than or equal to] d([v.sub.k]),

where i + 1 [less than or equal to] k [less than or equal to] t + 1 - i and i = 1,2,... , |(t + 1)/2].

Proof: We prove the result by induction oni. Fori = 1, suppose the opposite that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for 2 [less than or equal to] k [less than or equal to] t - 1. Let [T.sup.0] be the tree obtained by operating S([v.sub.1],[v.sub.k]) to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Clearly, [T.sup.0] [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that the edges [v.sub.0][v.sub.1] and [v.sub.k][v.sub.k+1] in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are transformed to the edges [v.sub.0][v.sub.k] and [v.sub.1][v.sub.k+1] in [T.sup.0], respectively. Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This is a contradiction. Hence we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for 2 [less than or equal to] k [less than or equal to] t - 1. At the same time, we

have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Similarly, we also can verify [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for 2 [less than or equal to] k [less than or equal to] t - 1. Hence we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for 2 [less than or equal to] k [less than or equal to] t.

Now, assume that the result holds for any l [less than or equal to] i - 1. That is, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for l + 1 [less than or equal to] k [less than or equal to] t + 1 - l, l = 1, 2,... , [(t + 1)/2]. For l = i, we have to prove that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for i+1[less than or equal to] k [less than or equal to] t+l - i and i = 1, 2,... , [(t + 1)/2]. Suppose the opposite that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some i + 1 - k [less than or equal to] t + 1 - i. Let [T.sup.0] be the tree obtained by applying S([v.sub.i], [v.sub.k]) to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Clearly, [T.sup.0] [member of] [??]. Note that the edges [v.sub.i-1][v.sub.i] and [v.sub.k][v.sub.k+1] in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are transformed to the edges [v.sub.i-1][v.sub.k] and [v.sub.i][v.sub.k+1] in [T.sup.0], respectively. Moreover, by the inductive hypothesis, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This is a contradiction. Hence we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for i + 1[less than or equal to] k [less than or equal to] t + 1- i. At the same time, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By the same argument as above, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for i + 1 [less than or equal to] k [less than or equal to] t + 1 - i. Hence we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for i + 1 [less than or equal to] k [less than or equal to] t + 1 - i, i = 1, 2,... , [(t + 1)/2]. This completes the proof. []

Lemma 3.5 For any T [member of] [??] withuv, xy [member of] E(T) anduy, xv [??] E (T), let [T.sup.0] = T - uv - xy + uy + xv. If [d.sub.T](u) [greater than or equal to] [d.sub.T](x) [greater than or equal to] [d.sub.T](y) [greater than or equal to] [d.sub.T](v), then irr([T.sup.0]) = irr(T).

Proof: Note that d(u) [greater than or equal to] d(x) [greater than or equal to] d(y) [greater than or equal to] d(v). Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This completes the proof. []

Suppose that the degrees of the non-leaf vertices are given. The greedy tree is achieved by the following "greedy algorithm" [12, 13]:

(i) label the vertex with the largest degree as [v.sub.0,1] (the root);

(ii) label the neighbors of [v.sub.0,1] as [v.sub.1,1],[v.sub.1,2],... , assign the largest degrees available to them such that d([v.sub.1,1]) [greater than or equal to] d([v.sub.1,2]) [greater than or equal to]... ;

(iii) label the neighbors of v 11 (except [v.sub.0,1]) as [v.sub.2,1], [v.sub.2,2],... , such that they take all the largest degrees available and that d([v.sub.2,1]) [greater than or equal to] d([v.sub.2,2]) [greater than or equal to]... , then do the same for [v.sub.1,2], [v.sub.1,3],... ;

(iv) repeat (iii) for all the newly labelled vertices, always start with the neighbors of the labelled vertex with largest degree whose neighbors are not labelled yet.

Theorem 3.1 Among trees in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], there exists a greedy tree with minimum irregularity.

Proof: Firstly, by the definition of the greedy tree with a given degree sequence, we easily to see that the greedy tree satisfies the conditions in Lemma 3.4. However, there are many trees for which these conditions hold. Then by Lemma 3.5, the greedy trees with minimum irregularity are constructed among these trees. This completes the proof. []

Remark 3.1 In fact, there are many trees different from the greedy tree with a given degree sequence minimize irr(T). Following is an example which are two [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. One is obtained by the greedy algorithm with degree sequence [pi] = {4,4, 3, 3,3,3, 3, 2, 2,2,2}, also it is a greedy tree. The other one is not a greedy tree with the same degree sequence, which are shown in Fig. 6.

[FIGURE 6 OMITTED]

4 Maximal (or minimal) irregularity of graphs in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In this section, we explore some properties on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]), and construct the corresponding trees [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]).

We now explore some properties for trees in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For T [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], let [n.sub.i] be the number of vertices of degree i in T for i = 1,2,... , [[DELTA].sub.1]. Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This implies that

Proposition 4.1 For any tree T [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], k(T) [less than or equal to] [[n-2]/2]

Moreover, note that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This leads to the following conclusion.

Proposition 4.2 For any tree T [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [[DELTA].sub.1](T) [less than or equal to] n - 2k + 1.

4.1 Properties on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Lemma 4.1 For 1 < k [less than or equal to] [[n-2]/2], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has the following properties:

1. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] contains no vertex with degree 2;

2. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] contains at most one vertex of degree larger than 3.

Proof: (1) Assume that there exists v [member of] V([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let u [member of] V([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If u [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], let T' be the tree obtained from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by Separating an edge uv. Clearly, T' [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then Lemma 2.1 implies that irr(T') > irr([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]), a contradiction. If u [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then there exists a path contains u and v in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let v be the vertex connected to u via [w.sub.1] with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let T' = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Clearly, T' [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

a contradiction. Hence the result follows.

(2) Assume that there exists two vertices u, v [member of] V([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If u [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], without loss of generality, we assume that u = [v.sub.s]. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Clearly, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

a contradiction. If u [??] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Clearly, T' [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By the same argument as above, we have irr(T') > irr([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]). This is also a contradiction. Hence the result follows. []

Combing Proposition 4.1 and Lemma 4.1, we then have the following.

Theorem 4.1 For 1 [less than or equal to] k [less than or equal to] [[n-2]/2], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has the degree sequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Lemma 4.2 For any tree T [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with degree sequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where k [less than or equal to] [[n-2]/2], then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: Note that T with degree sequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then T has t = 2(n - 1) - [DELTA]1 - (k - 1)[[DELTA].sub.2] leaves. Assume that [u.sub.1] [member of] V(T) with d([u.sub.1]) = [[DELTA].sub.1]. Note that for any tree T [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], there are [[DELTA].sub.1] disjoint pendent paths which begin with the vertex [u.sub.1]. If one of them is [P.sub.1] = [u.sub.1][u.sub.2]... [u.sub.i][v.sub.j], where d([u.sub.i]) = [[DELTA].sub.2] for 2 [less than or equal to] i [less than or equal to] k, and d([v.sub.j]) = 1 for 1 [less than or equal to] j [less than or equal to] t. Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

if one of them is P2 = [u.sub.1][v.sub.j], where d([v.sub.j]) = 1. Then we have irr([P.sub.2]) = |d([u.sub.1]) - d([v.sub.j])| = [[DELTA].sub.1] - 1. Obviously, there is [[DELTA].sub.1] ([[DELTA].sub.1] - 1) contributes to irr(T), by the [[DELTA].sub.1] disjoint pendent paths which begin with the vertex [u.sub.1]. By the construction of trees, there are leaving t - [[DELTA].sub.1] pendent vertices which just adjacent to the vertices with degree [[DELTA].sub.2], then they have (t - [[DELTA].sub.1])([[DELTA].sub.2] - 1) contributes to irr(T). No matter how to construct the tree T, there are some edges as the edge [u.sub.i][u.sub.j] with d([u.sub.i]) = d([u.sub.j]) = [[DELTA].sub.2], and their balance is 0 as |d([u.sub.i]) - d([u.sub.j])| = 0. Therefore, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This completes the proof. []

Remark 4.1 In fact, Lemma 4.2 also holds for [[DELTA].sub.1] = [[DELTA].sub.2]. That is, for any tree T [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with degree sequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where k [less than or equal to] [[n-2]/2], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By Theorem 4.1 and Lemma 4.2, we then have the following.

Theorem 4.2 For any tree T [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where 1 [less than or equal to] k [less than or equal to] [[n-2]/2], we have

irr(T) [less than or equal to] [n.sup.2] + (1 - 4k)n + [4k.sup.2] - 2,

and the equality holds if and only if T has degree sequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Moreover, by Theorem 4.2 and Lemma 2.2, we have the following.

Corollary 4.1 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

4.2 Properties on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Lemma 4.3 For [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: Suppose that there exists u [member of] V([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let P = [v.sub.0][v.sub.1],... ,[v.sub.i-1]u(= [v.sub.i])[v.sub.i+1],... , [v.sub.1] be the longest path in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] that contains u. Let w1 be a pendent vertex connected to u via [u.sub.1] (it is possible that [w.sub.1] [equivalent to] [u.sub.1]) (Fig. 7). Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Clearly, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

a contradiction. This completes the proof. []

[FIGURE 7 OMITTED]

Theorem 4.3 For 1 [less than or equal to] k [less than or equal to] [[n-2]/2], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has the degree sequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: By Lemma 4.3, we assume that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has degree sequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where x, y are integers. Note that k + x + y = n and 3k + 2x + y = 2(n - 1). Those yield that x = n - 2k - 2 and y = k + 2. Hence the result holds. []

Theorem 4.4 For any T G [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where k [less than or equal to] [[n-2]/2], then we have irr(T) [greater than or equal to] 2k + 4,

and the equality holds if and only if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: By Theorem 4.3, for any T [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Moreover, by Theorem 3.1, for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], there exists a greedy tree T* such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By the construct of the greedy tree T* with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Hence the result follows. []

From the proof of Theorem 4.4, we know that irr(T*) is monotonically increasing on k. Hence we have the following.

Corollary 4.2 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Acknowledgements

The authors would like to thank the anonymous referees for their constructive corrections and valuable comments on this paper, which have considerably improved the presentation of this paper.

References

[1] H. Abdo, N. Cohen, D. Dimitrov, Bounds and computation of irregularity of a graph, Filomat, 28(2014), 1315-1322.

[2] H. Abdo, D. Dimitrov, The irregularity of graphs under graph operations, Discuss. Math. Graph Theory, 34(2014), 263-278.

[3] M. Albertson, The irregularity of a graph, Ars Combin., 46(1997), 219-225.

[4] C. Berge, Graphs and Hyper graphs, 2nd edn., North-Holland, Amsterdam, 1976.

[5] G. Chartrand, P. Erdos, How to define an irregularity graph, Coll. Math. J., 19(1988), 36-42.

[6] P. Hansen, H. Melot, Variable neighborhood search for extremal graphs 9. Bounding the irregularity of a graph, DIMACS Ser. Discrete Math. Theoret. Comput. Sci, 69(2005), 253-264.

[7] M.A. Henning, D. Rautenbach, On the irregularity of bipartite graphs, Discrete Math., 307(2007), 1467-1472.

[8] Y. Liu, J.-B. Lv, The effects on the irregularity of graphs with some transformations, J. Minnan Normal University, 4(2014), 8-14.

[9] W. Luo, B. Zhou, On the irregularity of trees and unicyclic graphs with given matching number, Util. Math., 83(2010), 141-147.

[10] M. Tavakoli, F. Rahbarnia, M. Mirzavaziri, A.R. Ashrafi, I. Gutman, Extremely irregular graphs, Kragujevac J. Math., 37(2013), 135-139.

[11] M. Tavakoli, F. Rahbarnia, A. R. Ashrafi, Some new results on irregularity of graphs, J. Appl. Math. Inform., 32(2014), 675-685.

[12] H. Wang, Extremal trees with given degree sequence for the Randic index, Discrete Math., 308(2008), 3407-3411.

[13] R. Xing, B. Zhou, Extremal trees with fixed degree sequence for atom-bond connectivity index, Filomat, 26(2012), 683-688.

[14] B. Zhou, On irregularity of graphs, Ars Combin., 88(2008), 55-64.

Jianxi Li (1*) Yang Liu (1) Wai Chee Shiu (2)

(1) School of Mathematics and Statistics, Minnan Normal University, Zhangzhou, Fujian, P.R. China

(2) Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong, P.R. China.

received 23rd June 2015, revised 27th Mar. 2016, accepted 2nd June 2016.

(*) This work is partially supported by NSF of China (Nos.11101358, 61379021, 11471077); NSF of Fujian (Nos.2014J01020, 2015J01018, 2016J01673); China Postdoctoral Science Foundation (No.2014M551831); General Research Fund of Hong Kong and Faculty Research Grant of Hong Kong Baptist University.
COPYRIGHT 2016 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Li, Jianxi; Liu, Yang; Shiu, Wai Chee
Publication:DMTCS Proceedings
Article Type:Report
Date:Jan 1, 2016
Words:6058
Previous Article:A proof of Zhil'tsov's theorem on decidability of equational theory of epigroups.
Next Article:The inapproximability for the (0,1)-additive number.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters