Limites da Energia de Cor

Prévia do material em texto

Chapter 2
Bounds of color energy
The concept of color energy of a graph G is based on the color matrix of G. For a given
graph G, the color energy Ec(G) is the sum of the absolute values of eigenvalues of color
matrix of G. Naturally, the values of the color energy of a graph G depends upon the
coloring given to G. If all the vertices of a graph G receive same color, then the value
of the color energy for G would be minimum, say x and if all the vertices of G receive
different colors, then the value of its color energy would be maximum, say y. Therefore,
these values x and y provide the trivial bounds for the color energy of G. The bounds give
an idea about the range of values of color energy of G.
In this chapter, we include the results for bounds of color energy in terms of several
graph theoretic parameters such as order, size, chromatic number, independence number,
domination number, etc. Moreover, the results for bounds of color energy in terms of
some specific eigenvalues are also presented.
2.1 Bounds in terms of order and size
This section deals with some upper and lower bounds of color energy of a graph G in
terms of its order n and size m. We begin with an upper bound of color energy in terms of
the order n.
Chapter 2. Bounds of color energy
Theorem 2.1.1. Let G be a graph of order n. Then
Ec(G)≤ n(n−1). (2.1)
Proof. Let Ac(G) be the color matrix of a graph G such that λ1,λ2,λ3, . . . ,λn are its
eigenvalues. Let Ri be the sum of absolute values of the entries of Ac(G) in the ith row
and R = max
i
Ri, for 1 ≤ i ≤ n.
By Theorem 1.1.5 (ii),
|λi| ≤ R, for 1 ≤ i ≤ n. (2.2)
By the definition of Ac(G), each off-diagonal element in Ac(G) is from the set {1,−1,0}
and each diagonal element of Ac(G) is 0. Therefore, the maximum possible value of R is
n−1. Thus by Equation (2.2)
|λi| ≤ n−1, for 1 ≤ i ≤ n
n
∑
i=1
|λi| ≤ n(n−1).
Hence,
Ec(G)≤ n(n−1).
It is to be observed that the upper bound given in Theorem 2.1.1 is sharp for graphs K2
and K1∪K1. In the next lemma, we prove an upper bound of sum of squares of eigenvalues
of color matrix of a graph G in terms of its order.
Lemma 2.1.2. If G is a graph of order n and λ1,λ2,λ3, . . . ,λn are the eigenvalues of
Ac(G), then
n
∑
i=1
λ
2
i ≤ n(n−1).
27
Chapter 2. Bounds of color energy
Proof. By Definition 1.1.4, the color matrix Ac(G) is symmetric. Therefore, it is a normal
matrix. Thus, by Theorem 1.1.5 (iii),
n
∑
i=1
|λi|2 =
n
∑
i, j
|ai j|2. (2.3)
There are n2 entries in Ac(G). Each off-diagonal entry would contribute maximum value
1, and the diagonal entry would contribute 0 to the quantity
n
∑
i, j
|ai j|2. Therefore,
n
∑
i, j
|ai j|2 ≤ n2 −n. (2.4)
Thus by Equations (2.3) and (2.4),
n
∑
i=1
|λi|2 ≤ n(n−1).
Hence, the result holds.
Remark 2.1.3. We can prove Theorem 2.1.1 by using Lemma 2.1.2. By Proposition 1.3.7
and Theorem 1.3.9,
Ec(G)≤
n
∑
i=1
λ
2
i . (2.5)
Therefore, by Lemma 2.1.2 and Equation (2.5)
Ec(G)≤ n(n−1).
Next, we derive an upper bound for color energy of a graph G in terms of its order n
and the number m′
c of pairs of non-adjacent vertices receiving same color.
28
Chapter 2. Bounds of color energy
Theorem 2.1.4. Let G be a graph order n. Then
Ec (G)≤
[
n
(
n2 −n+2m′
c
)] 1
2 . (2.6)
Proof. For a simple graph G, 2m ≤ n2 −n. Therefore,
n(2m+2m′
c)≤ n(n2 −n+2m′
c)√
2n(m+m′
c)≤
√
n(n2 −n+2m′
c). (2.7)
Therefore, by Equation (2.7) and Theorem 1.3.8
Ec(G)≤
√
n(n2 −n+2m′
c).
The upper bound of color energy given in Equation (2.6) is an improvement on the
upper bound mentioned in Equation (2.1). For example, let B be the bow-tie graph with
respect to a proper vertex coloring corresponding to minimum number of colors χ(B) = 3.
It is depicted in Figure 2.1. The eigenvalues of color matrix of B are 0,−2,−2,2,2 and
the color energy of B corresponding to minimum number of colors, Eχ(B) = 8. Equations
(2.1) and (2.6) give the value of the upper bound as 20 and 10.95 respectively. Clearly,
Eχ(B) = 8 ≤ 10.95 ≤ 20. Therefore, Equation (2.6) provides a tighter upper bound than
that given by Equation (2.1).
1
2
3
2
3
FIGURE 2.1: Bow-tie graph B with χ(B) = 3
29
Chapter 2. Bounds of color energy
The next theorem provides a lower bound for color energy of a graph G in terms of
size m and m′
c, which is the number of pairs of non-adjacent vertices receiving same color.
Theorem 2.1.5. Let G be a graph of size m. Then
Ec(G)≥
√
2(m+m′
c). (2.8)
Proof. By Proposition 1.3.7,
n
∑
i=1
λ
2
i = 2(m+m′
c) (2.9)
and by Lemma 1.1.10 √
n
∑
i=1
|λi|2 ≤
n
∑
i=1
|λi|. (2.10)
Therefore, by Equations (2.9) and (2.10),
Ec(G) =
n
∑
i=1
|λi| ≥
√
n
∑
i=1
|λi|2 =
√
2(m+m′
c).
Hence,
Ec(G)≥
√
2(m+m′
c).
We have observed that if the determinant of the color matrix of a given graph is zero,
then the lower bound provided in Theorem 2.1.5 coincides with the lower bound given
in Theorem 1.3.8. For example, let T4,1 be the (4,1)-tadpole graph having chromatic
number χ(T4,1) = 2 as shown in Figure 2.2. The eigenvalues of color matrix of T4,1 are
0,1,1,−1+
√
7,−1−
√
7. Therefore, the color energy of T4,1 with respect to minimum
number of colors Eχ(T4,1) = 7.3. As one of the eigenvalue is 0, the determinant of the
30
Chapter 2. Bounds of color energy
color matrix D is 0. Therefore,
√
2(m+m′
c)+n(n−1)D
2
n =
√
2(m+m′
c).
Thus both the lower bounds given in Equations (1.6) and (2.8) coincide and show the
value 4.243 for the lower bound of color energy of T4,1.
2
2
1
1 1
FIGURE 2.2: (4,1)-tadpole graph T4,1 with χ(T4,1) = 2
In the following theorem, we provide an alternative proof of the upper bound stated in
the Theorem 1.3.8. Note that, m′
c is the number of pairs of non-adjacent vertices having
same color.
Theorem 2.1.6. Let G be a graph of order n and size m. Then
Ec(G)≤
√
2n(m+m′
c).
Proof. By Holder’s inequality stated in Lemma 1.1.9,
n
∑
i=1
xiyi ≤
( n
∑
i=1
xp
i
)1/p( n
∑
i=1
yq
i
)1/q
. (2.11)
31
Chapter 2. Bounds of color energy
Let λ1,λ2, . . . ,λn be the eigenvalues of Ac(G). Consider xi = |λi|, yi = 1 and p = q = 2.
Then by Equation (2.11),
n
∑
i=1
|λi| ≤
( n
∑
i=1
|λi|2
)1/2( n
∑
i=1
12)1/2
Ec(G)≤ n1/2( n
∑
i=1
|λi|2
)1/2
. (2.12)
By Proposition 1.3.7,
n
∑
i=1
λ
2
i = 2(m+m′
c). (2.13)
Therefore, by Equations (2.12) and (2.13),
Ec(G)≤ n1/2[2(m+m′
c)
1/2]
Ec(G)≤
√
2n(m+m′
c).
2.2 Bounds in terms of chromatic number and indepen-
dence number
In this section, we derive upper and lower bounds of color energy of a graph G in terms
of its chromatic number χ(G) and independence number α(G). We begin the section by
presenting a lower bound for color energy of a graph in terms of its chromatic number.
Theorem 2.2.1. If G is a graph of order n with D ≥ 0, where D is the determinant of
Ac(G), then
χ(G)≤ Ec(G).
32
Chapter 2. Bounds of color energy
Proof. By the arithmetic and geometric means, for eigenvalues λ1,λ2, . . . ,λn of Ac(G)
1
n
n
∑
i=1
|λi| ≥
( n
∏
i=1
|λi|
) 1
n
1
n
Ec(G)≥ D
1
n .
Since D ≥ 0,
Ec(G)≥ n. (2.14)
By Theorem 1.2.4,
χ(G)≤ n. (2.15)
Thus, by Equations (2.14) and (2.15)
χ(G)≤ Ec(G).
The following theorem provides an upper bound of color energy of a graph G in terms
of its chromatic number χ(G), independence number α(G), order m and m′
c which is the
number of pairs of non-adjacent vertices in G having same color.
Theorem 2.2.2. Let G be a graph of order n and size m. Then
Ec (G)≤
[
2χ (G)α (G)
(
m+m′
c
)] 1
2 .
33
Chapter 2. Bounds of color energy
Proof. By Theorem 1.2.4 (ii),
n
α(G)
≤ χ(G)
n ≤ χ(G)α(G)
2n(m+m′
c)≤ 2χ(G)α(G)(m+m′
c)√
2n(m+m′
c)≤
√
2χ(G)α(G)(m+m′
c). (2.16)
Therefore, by Equation (2.16) and Theorem 1.3.8
Ec(G)≤
√
2χ(G)α(G)(m+m′
c). (2.17)
In the next theorem, we derive a lower bound of color energy in terms of χ(G), m, m′
c
and the determinant D of Ac(G).
Theorem 2.2.3. Let G be a graph of order n and size m. Then
Ec (G)≥
{
2
(
m+m′
c
)
+χ (G) [χ(G)−1]D
(
2
χ(G)
)} 1
2
.
Proof. By Theorem 1.3.8,Ec(G)≥
√
2(m+m′
c)+n(n−1)D2/n (2.18)
and by Theorem 1.2.4 (i),
χ(G)≤ n. (2.19)
34
Chapter 2. Bounds of color energy
Therefore, by Equations (2.18) and (2.19)
Ec(G)≥
{
2(m+m′
c)+χ (G) [χ(G)−1]D
(
2
χ(G)
)} 1
2
.
2.3 Bounds in terms of domination number and maxi-
mum degree
In this section, we obtain bounds for color energy of a graph G in terms of domination
number γ(G) and maximum degree ∆(G) of the graph under consideration. Throughout
this section, m and m′
c are the size of a graph G and the number of pairs of non-adjacent
vertices in G receiving same color, respectively.
In the following theorem, a lower bound of color energy of a graph G in terms of its
domination number γ(G), order n, size m and m′
c is derived.
Theorem 2.3.1. If G is a graph of order n, size m and has no isolated vertices, then
Ec (G)≥
γ (G)
√
2(m+m′
c)
n
.
Proof. If G has no isolated vertices, then by Theorem 1.1.1 (ii)
2γ(G)≤ n
4γ(G)
√
m+m′
c ≤ 2n
√
m+m′
c
γ(G)
n
√
2(m+m′
c)≤ 2
√
m+m′
c. (2.20)
35
Chapter 2. Bounds of color energy
By Theorem 1.3.9,
2
√
m+m′
c ≤ Ec(G). (2.21)
Therefore, by Equations (2.20) and (2.21)
γ(G)
n
√
2(m+m′
c)≤ Ec(G).
Hence, the result holds.
The next theorem provides a bound for color energy of a graph G in terms of its
domination number γ(G), maximum degree ∆(G), size m and m′
c.
Theorem 2.3.2. Let G be a graph of order n and size m. Then
Ec (G) ≤
[
2(1+∆(G)γ (G)
(
m+m′
c
)] 1
2 .
Proof. By Theorems 1.1.1 and 1.2.4,
χ(G)≥ n
α(G)
≥ n
γ(G)
α(G)≤ γ(G) (2.22)
By Theorem 1.2.4 (iii) and Equation (2.22),
n ≤ χ(G)α(G)≤ χ(G)γ(G). (2.23)
Thus, by Theorem 1.3.8 and Equation (2.23),
Ec(G)≤
√
2χ(G)γ(G)(m+m′
c). (2.24)
36
Chapter 2. Bounds of color energy
Hence, by Theorem (1.2.4) (iv) and Equation (2.24)
Ec(G)≤
√
2(1+∆(G))γ(G)(m+m′
c).
The results mentioned in the succeeding theorem give an upper bound for color energy
of a graph G in terms of its size m, γ(G), ∆(G), m′
c and the determinant D of the color
matrix Ac(G).
Theorem 2.3.3. Let G be a graph of order n and size m. Then
(i) Ec (G)≥
{
[∆(G)+ γ (G)] [∆(G)+ γ (G)−1]D
(
2
∆(G)+γ(G)
)
+2(m+m′
c)
} 1
2
.
(ii) Ec (G)≥
{
2(m+m′
c)+2γ (G) [2γ (G)−1]D
(
1
γ(G)
)} 1
2
, provided G has no isolated
vertices.
Proof. (i) By Theorem 1.1.1 (i),
∆(G)+ γ(G)≤ n (2.25)
and by Theorem 1.3.8,
Ec(G)≥
√
2(m+m′
c)+n(n−1)D2/n. (2.26)
Therefore, by Equations (2.25) and (2.26),
Ec (G)≥
{
[∆(G)+ γ (G)] [∆(G)+ γ (G)−1]D
(
2
∆(G)+γ(G)
)
+2
(
m+m′
c
)} 1
2
.
37
Chapter 2. Bounds of color energy
(ii) If G is a graph with no isolated vertices, then by Theorem 1.1.1 (ii)
n ≥ 2γ(G). (2.27)
Hence, by Theorem 1.3.8 and Equation (2.27)
Ec(G)≥
√
2(m+m′
c)+2γ(G)[2γ(G)−1]D
(
1
γ(G)
)
.
2.4 Bounds in terms of extreme eigenvalues
Some upper and lower bounds of color energy of a graph G in terms of λmax and λmin
are included in this section. By λmax and λmin, we mean largest and least absolute values
of eigenvalues of color matrix of G. It is to be noted that m′
c is the number of pairs of
non-adjacent vertices having same color.
The subsequent theorems, namely Theorem 2.4.1 and Theorem 2.4.2, present lower
bounds of color energy of a graph G in terms of its order n, size m, m′
c, λmin and λmax.
Theorem 2.4.1. Let G be a graph of order n and size m. Then
(i)
Ec(G)≥
 8n(m+m′
c)√
λmax
λmin
+
√
λmin
λmax

1/2
,
(ii)
Ec(G)≥
√
n
2
{
8n(m+m′
c)−n(λmax −λmin)
2
}1/2
.
38
Chapter 2. Bounds of color energy
Proof. By Lemma 1.1.11, we have
n
∑
i=1
(ai)
2
n
∑
i=1
(bi)
2 ≤ 1
4
(√
M1M2
m1m2
+
√
m1m2
M1M2
)( n
∑
i=1
aibi
)2
(2.28)
and
n
∑
i=1
(ai)
2
n
∑
i=1
(bi)
2 −
( n
∑
i=1
aibi
)2 ≤ n2
4
(
m1m2 −M1M2
)2
, (2.29)
where ai and bi are positive real numbers and M1 = max
1≤i≤n(ai), M2 = max
1≤i≤n(bi), m1 =
min
1≤i≤n(ai) and m2 = min
1≤i≤n(bi), for 1 ≤ i ≤ n.
Let λ1,λ2, . . . ,λn be the eigenvalues of color matrix of the graph G. Consider ai = |λi|
and bi = 1 for 1 ≤ i ≤ n. Then M1 = λmax, M2 = 1 and m1 = λmin, m2 = 1.
(i) By Equation (2.28),
n
∑
i=1
|λi|2
n
∑
i=1
(1)2 ≤ 1
4
(√
λmax
λmin
+
√
λmin
λmax
)( n
∑
i=1
|λi|
)2
n
n
∑
i=1
|λi|2 ≤
1
4
(√
λmax
λmin
+
√
λmin
λmax
)(
Ec(G)
)2
.
Thus,
(
Ec(G)
)2
≥ 4n∑
n
i=1 |λi|2√
λmax
λmin
+
√
λmin
λmax
. (2.30)
By Proposition 1.3.7 and Equation (2.30),
(
Ec(G)
)2
≥ 8n(m+m′
c)√
λmax
λmin
+
√
λmin
λmax
Ec(G)≥
 8n(m+m′
c)√
λmax
λmin
+
√
λmin
λmax

1/2
.
39
Chapter 2. Bounds of color energy
(ii) By Equation (2.29),
n
∑
i=1
|λi|2
n
∑
i=1
(1)2 −
( n
∑
i=1
|λi|
)2 ≤ n2
4
(
λmin −λmax
)2
n
n
∑
i=1
|λi|2 −
(
Ec(G)
)2 ≤ n2
4
(
λmin −λmax
)2
. (2.31)
Therefore, by Proposition 1.3.7 and Equation (2.31),
(
Ec(G)
)2 ≥ 2n(m+m′
c)−
n2
4
(
λmin −λmax
)2
Ec(G)≥
√
n
2
{
8n(m+m′
c)−n(λmax −λmin)
2
}1/2
.
Theorem 2.4.2. Let G be a graph of order n and size m. Then
Ec(G)≥ n+2λmaxλmin(m+m′
c)
λmax +λmin
.
Proof. By Lemma 1.1.12,
n
∑
i=1
(ai)
2 +ab
n
∑
i=1
(bi)
2 ≤ (a+b)
n
∑
i=1
aibi. (2.32)
where ai ̸= 0, a ≤ bi
ai
≤ b, for 1 ≤ i ≤ n.
Let λ1,λ2, . . . ,λn be the eigenvalues of the color matrix of a graph G and bi = |λi| and
ai = 1 for 1 ≤ i ≤ n. Therefore, we consider a = λmin and b = λmax. Thus, by Equation
(2.32),
n
∑
i=1
(1)2 +λminλmax
n
∑
i=1
|λi|2 ≤ (λmin +λmax)
n
∑
i=1
|λi|. (2.33)
40
Chapter 2. Bounds of color energy
Therefore, by Proposition 1.3.7 and Equation (2.33)
n+2λminλmax(m+m′
c)≤ (λmin +λmax)Ec(G)
Ec(G)≥ n+2λmaxλmin(m+m′
c)
λmax +λmin
.
The upper bounds of color energy of a graph G in terms of its order n, λmin, λmax and
µmax, which is the largest absolute value among eigenvalues of A−1
c (G) is obtained in the
succeeding theorems.
Theorem 2.4.3. Let G be a graph of order n and size m. Then
Ec(G)≤ n(λmax +λmin)
4λmaxλminµmax
,
where µmax is the largest absolute value among eigenvalues of A−1
c (G).
Proof. By Lemma 1.1.13 (i),
(
1
n
n
∑
i=1
ai
)(
1
n
n
∑
i=1
1
ai
)
≤ (a+b)2
4ab
(2.34)
where 0 ≤ a ≤ ai ≤ b, for i = 1,2, . . . ,n. Let’s consider ai = |λi| for 1 ≤ i ≤ n, where λi’s
are the eigenvalues of Ac(G). Thus, a = λmin and b = λmax. Therefore,
(
1
n
n
∑
i=1
|λi|
)(
1
n
n
∑
i=1
1
|λi|
)
≤ (λmin +λmax)
2
4λminλmax(
1
n
Ec(G)
)(
1
n
n
∑
i=1
µmax
)
≤ (λmin +λmax)
2
4λminλmax
,
41
Chapter 2. Bounds of color energy
where µmax is the largest absolute value among eigenvalues of A−1
c (G). Thus,
Ec(G)≤ n2(λmax +λmin)
4λmaxλmin
n
∑
i=1
µmax
Ec(G)≤ n2(λmax +λmin)
4nλmaxλminµmax
. (2.35)
Since µmax is constant, ∑
n
i=1 µmax = nµmax. Therefore, by Equation (2.35)
Ec(G)≤ n(λmax +λmin)
4λmaxλminµmax
.
Theorem 2.4.4. Let G be a graph of order n. Then
Ec(G)≤
n
([n
2
]2
+
[n+1
2
]2
)
µmax
+n
[
n
2
][
n+1
2
](λ 2
max +λ 2
min
)
λminλmaxµmax
,
where µmax is the largest absolute value of eigenvalue of A−1
c (G) and,[
n
2
]
and
[
n+1
2
]
is the greatest integer less than or equal to n
2 and n+1
2 .
Proof. By Lemma 1.1.13 (ii),
(
1
n
n
∑
i=1
ai
)(
1
n
n
∑
i=1
1
ai
)
≤
(
[n
2 ]b+[n+1
2 ]a
)(
[n+1
2 ]b+[n
2 ]a
)
ab
, (2.36)
where [x] represents the integral part the real number x and ai is a real number such that
0 ≤ a ≤ ai ≤ b for 1 ≤ i ≤ n.
Let ai = |λi| for 1 ≤ i ≤ n, where λi’s are the eigenvalues of Ac(G) and, a = λmin and
b = λmax.
42
Chapter 2. Bounds of color energy
Therefore,
(
1
n
n
∑
i=1
|λi|
)(
1
n
n
∑
i=1
1
|λi|
)
≤
(
[n
2 ]b+[n+1
2 ]λmin
)(
[n+1
2 ]λmax +[n
2 ]λmin
)
λminλmax
1
n2 Ec(G)
n
∑
i=1
1
|λi|
≤
(
[n
2 ]b+[n+1
2 ]λmin
)(
[n+1
2 ]λmax +[n
2 ]λmin
)
λminλmax
(2.37)
Let µmax is the largest absolute value of A−1
c (G). Then by Equation (2.37),
1
n2 Ec(G)
n
∑
i=1
µmax ≤
(
[n
2 ]b+[n+1
2 ]λmin
)(
[n+1
2 ]λmax +[n
2 ]λmin
)
λminλmax
1
n
Ec(G)µmax ≤
(
[n
2 ]λmax +[n+1
2 ]λmin
)(
[n+1
2 ]λmax +[n
2 ]λmin
)
λminλmax
Ec(G)≤ n
(
[n
2 ]λmax +[n+1
2 ]λmin
)(
[n+1
2 ]λmax +[n
2 ]λmin
)
λminλmaxµmax
(2.38)
Since µmax is a constant, by Equation (2.38)
Ec(G)≤n
([n
2
][n+1
2
]
λ 2
max +
[n
2
]2
λminλmax +
[n+1
2
]2
λmaxλmin +
[n+1
2
][n
2
]
λ 2
min
)
λminλmaxµmax
.
Thus,
Ec(G)≤n

([n
2
]2
λminλmax +
[n+1
2
]2
λmaxλmin
)
λminλmaxµmax
+
([n
2
][n+1
2
]
λ 2
max +
[n+1
2
][n
2
]
λ 2
min
)
λminλmaxµmax
 .
Hence,
Ec(G)≤
n
([
n
2
]2
+
[
n+1
2
]2)
µmax
+n
[
n
2
][
n+1
2
](λ 2
max +λ 2
min
)
λminλmaxµmax
.
43