Bulletin T.CXXXIII de l’Académie serbe des sciences et des arts − 2006 Classe des Sciences mathématiques et naturelles Sciences mathématiques, N\underline{o} 31

INEQUALITIES BETWEEN DISTANCE–BASED GRAPH POLYNOMIALS

I. GUTMAN, OLGA MILJKOVIĆ, B. ZHOU, M. PETROVIĆ

(Presented at the 2nd Meeting, held on March 24, 2006)

A b s t r a c t. In a recent paper [ I. Gutman, Bull. Acad. Serbe Sci. Arts (Cl. Math. Natur.) 131 (2005) 1–7], the Hosoya polynomial H = H(G, λ) of a graph G, and two related distance–based polynomials H_{1} = H_{1}(G, λ) and H_{2} = H_{2}(G, λ) were examined. We now show that

max{δ H_{1} − δ^{2} H , Δ H_{1} − Δ^{2} H} ≤ H_{2} ≤ Δ H_{1} − δ Δ H

holds for all graphs G and for all λ ≥ 0 , where δ and Δ are the smallest and greatest vertex degree in G. The answer to the question which of the terms δ H_{1} − δ^{2} H and Δ H_{1} − Δ^{2} H is greater, depends on the graph G and on the value of the variable λ. We find a number of particular solutions of this problem.

AMS Mathematics Subject Classification (2000): 05C12, 05C05 Key Words: Graph polynomial, distance (in graph)

1. Introduction

In a recent paper [1] some distance–based graph polynomials were studied and relations between them established. We now obtain inequalities between these polynomials.

We use the same notation and terminology as in [1]: By G is denoted a connected graph, V (G) its vertex set, E(G) its edge set, n the number of its vertices, and m the number of its edges. By δ_{x} is denoted the degree of the vertex x ∈ V (G) . The smallest and greatest vertex degree in the graph G are δ and Δ , respectively.

The distance between the vertices x and y of the graph G is denoted by d(x, y) . Because the graph G is assumed to be connected, the distance d(x, y) is a well-defined quantity for all pairs of vertices x and y. In particular, if x = y, then d(x, y) = 0 . The greatest distance in G is its diameter and will be denoted by D. The number of pairs of vertices of G that are at distance k is denoted by d(G, k) .

The Hosoya polynomial (originally called “Wiener polynomial” [2]) of a graph G is defined as

H = H(G, λ) = ∑_{k≥0} d(G, k) λ^{k} .  (1)

This graph polynomial was much studied in the past [3–10].

Another way in which the right–hand side of Eq. (1) can be written is

H(G, λ) = ∑_{{x,y}⊆V (G)} λ^{d(x,y)} .  (2)

The expression (2) made it possible [1] to conceive two other, closely related graph polynomials, viz.,

H_{1} = H_{1}(G, λ) = ∑_{{x,y}⊆V (G)}(δ_{x} + δ_{y}) λ^{d(x,y)}  (3)

and

H_{2} = H_{2}(G, λ) = ∑_{{x,y}⊆V (G)} δ_{x} δ_{y} λ^{d(x,y)} .  (4)

Let P = P (λ) be a polynomial of the form

P (λ) = ∑_{k=0}^{n} a_{k} λ^{k}

Then we write a_{k} = coeff_{k}(P) . With this notation, in view of Eqs. (2) and (3), it is elementary to verify the following:

coeff_{0}(H) = n  ;  coeff_{1}(H) = m  (5)
coeff_{0}(H_{1}) = 4m  ;  coeff_{1}(H_{1}) = ∑_{x∈V (G)}(δ_{x})^{2} . (6)

The second relation in (6) is a consequence of

∑_{xy∈E(G)}(δ_{x} + δ_{y}) = ∑_{x∈V (G)}(δ_{x})^{2} .

A graph is said to be regular of degree r if all its vertices have degrees equal to r. In this case the above defined graph polynomials are simply related as

H_{1} = 2r H  and  H_{2} = r^{2} H .

In view of this, in what follows we shall assume that the graphs considered are non-regular, which is tantamount to the requirement δ < Δ .

2. Elementary Inequalities between the Polynomials H , H_{1} , and H_{2}

For any vertex x ∈ V (G) , δ ≤ δ_{x} ≤ Δ . Therefore, for any pair of (not necessarily distinct) vertices x, y ∈ V (G) ,

(δ_{x} − δ)(δ_{y} − δ) ≥ 0  (7)
(δ_{x} − Δ)(δ_{y} − Δ) ≥ 0  (8)
(δ_{x} − δ)(δ_{y} − Δ) ≤ 0 .  (9)

From (7) and (8) there follows

δ_{x} δ_{y} − δ (δ_{x} + δ_{y}) + δ^{2} ≥ 0
δ_{x} δ_{y} − Δ (δ_{x} + δ_{y}) + Δ^{2} ≥ 0,

which in view of Eqs. (2)–(4) and assuming that λ ≥ 0 immediately yields

H_{2} − δ H_{1} + δ^{2} H ≥ 0  (10)
H_{2} − Δ H_{1} + Δ^{2} H ≥ 0 .  (11)

From (9) one obtains

δ_{x} δ_{y} − (Δ δ_{x} + δ δ_{y}) + δ Δ ≤ 0

from which there follows a weaker inequality

δ_{x} δ_{y} − Δ (δ_{x} + δ_{y}) + δ Δ ≤ 0

which, in turn, implies

H_{2} − Δ H_{1} + δ Δ H ≤ 0 .  (12)

Bearing in mind the inequalities (10)–(12) we have

Theorem 1. Let δ and Δ be, respectively, the smallest and the greatest vertex degree in the graph G. Then for any connected graph G and all λ ≥ 0 ,

max{δ H_{1}(G, λ) − δ^{2} H(G, λ) , Δ H_{1}(G, λ) − Δ^{2} H(G, λ)} ≤ H_{2}(G, λ)
≤ Δ H_{1}(G, λ) − δ Δ H(G, λ) .

Finding which of the two terms in the lower bound in Theorem 1 is greater, appears to be a difficult task. Anyway, it is either

max{δ H_{1} − δ^{2} H , Δ H_{1} − Δ^{2} H} = δ H_{1} − δ^{2} H  (13)

or

max{δ H_{1} − δ^{2} H , Δ H_{1} − Δ^{2} H} = Δ H_{1} − Δ^{2} H .  (14)

Comparing the right–hand sides of (13) and (14), and taking into account that Δ − δ > 0 , we arrive at the following auxiliary

Lemma 2. If (δ + Δ) H(G, λ) > H_{1}(G, λ) , then Eq. (13) holds. If (δ + Δ) H(G, λ) < H_{1}(G, λ) , then Eq. (14) holds. If (δ + Δ) H(G, λ) = H_{1}(G, λ) , then both Eqs. (13) and (14) are applicable.

If Eqs. (13) and (14) simultaneously hold, then

(δ + Δ) H(G, λ) − H_{1}(G, λ) = 0 .  (15)

The real non-negative solutions of Eq. (15) (if any) will be referred to as the critical values of the graph G.

In what follows we examine the conditions for the validity of (13) and (14). The following example reveals that these conditions are far from being trivial.

Example 1. Let P_{n} be the n-vertex path and let n ≥ 3 . Then δ = 1 and Δ = 2 . It can be shown that

H(P_{n}, λ) = ∑_{k=0}^{n−1}(n−k) λ^{k}  and  H_{1}(P_{n}, λ) = 4n−4+∑_{k=1}^{n−1}(4n−2−4k) λ^{k} .

Thus, in the case n = 3 ,

(δ + Δ) H(P_{n}, λ) = 9 + 6 λ + 3 λ^{2}
H_{1}(P_{n}, λ) = 8 + 6 λ + 2 λ^{2}

and thus Eq. (13) holds for all values of the variable λ , λ ≥ 0 . The path P_{3} has no critical values.

In the case n = 4 we have

(δ + Δ) H(P_{n}, λ) = 12 + 9 λ + 6 λ^{2} + 3 λ^{3}
H_{1}(P_{n}, λ) = 12 + 10 λ + 6 λ^{2} + 2 λ^{3} .

Consequently, Eq. (14) holds for near-zero (positive) values of the variable λ, whereas (13) holds if λ is sufficiently large. By a detailed examination we find that Eq. (14) holds for 0 < λ < 1 , and Eq. (13) holds for λ > 1 . The path P_{4} has two critical values, λ_{1}(P_{4}) = 0 and λ_{2}(P_{4}) = 1 .

In the case n = 5 the situation is slightly different: (14) holds for 0 ≤ λ < λ_{1} , (13) holds for λ > λ_{1} , and there is only a single critical value λ_{1}(P_{5}) = (1 + \sqrt{5})/2 .

The problem of establishing which of the Eqs. (13) and (14) is valid becomes much less perplexed if one restricts the consideration to near zero (positive) and to very large values of the variable λ.

Lemma 3. If λ is sufficiently close to zero (but positive–valued), then

(δ + Δ) coeff_{0}(H) > coeff_{0}(H_{1})  (16)

implies the validity of Eq. (13), and

(δ + Δ) coeff_{0}(H) < coeff_{0}(H_{1})  (17)

implies the validity of Eq. (14). If

(δ + Δ) coeff_{0}(H) = coeff_{0}(H_{1})  (18)

then

(δ + Δ) coeff_{1}(H) > coeff_{1}(H_{1})  (19)

implies the validity of Eq. (13), and

(δ + Δ) coeff_{1}(H) < coeff_{1}(H_{1})  (20)

implies the validity of Eq. (14). If also

(δ + Δ) coeff_{1}(H) = coeff_{1}(H_{1})  (21)

then one has to compare the second coefficients of H(G, λ) and H_{1}(G, λ) , etc.

With regard to conditions (18)–(21) see Lemma 5.

Lemma 4. Let D be the diameter of the graph G under consideration. If λ is sufficiently large, then

(δ + Δ) coeff_{D}(H) > coeff_{D}(H_{1})  (22)

implies the validity of Eq. (13), and

(δ + Δ) coeff_{D}(H) < coeff_{D}(H_{1})

implies the validity of Eq. (14). If

(δ + Δ) coeff_{D}(H) = coeff_{D}(H_{1})

then

(δ + Δ) coeff_{D−1}(H) > coeff_{D−1}(H_{1})

implies the validity of Eq. (13), and

(δ + Δ) coeff_{D−1}(H) < coeff_{D−1}(H_{1})

implies the validity of Eq. (14). If also

(δ + Δ) coeff_{D−1}(H) = coeff_{D−1}(H_{1})

then one has to compare the third-last coefficients of H(G, λ) and H_{1}(G, λ) , etc.

Lemma 5. For any connected and non-regular graph, the validity of Eq.

(18) implies the validity of (20), i.e., if (18) holds, then conditions (19) and (21) never occur.

P r o o f. Bearing in mind (5) and (6) we immediately see that (18) is equivalent to

(δ + Δ) n = 4m.  (23)

Now, knowing that ∑_{x∈V (G)} δ_{x} = 2m, we have

∑_{x∈V (G)}(δ_{x})^{2} = ∑_{x∈V (G)} (δ_{x} − \frac{2m}{n})^{2} + \frac{4m^{2}}{n}

which (for non-regular graphs) implies

∑_{x∈V (G)}(δ_{x})^{2} > \frac{4m^{2}}{n} .

Combining this inequality with (23), we get

∑_{x∈V (G)}(δ_{x})^{2} > (δ + Δ) m

which is equivalent with (20). □

* * * * *

Relation (23) determines the condition under which a graph has a critical value equal to zero.

In the case of trees, δ = 1 , m = n − 1 , and (23) becomes

(3 − Δ)n = 4 .

This condition is obeyed only if Δ = 2 and n = 4 , i.e., among all trees only the 4-vertex path has a zero critical value.

In the case of unicyclic graphs (different from C_{n}), δ = 1 and m = n. Then from (23) follows Δ = 3 . Thus, connected unicyclic graphs with maximum vertex degree 3 have a zero critical value. Those with maximum vertex degree greater than 3 have no such critical value.

In the case of bicyclic graphs, m = n + 1 and (23) yields

(δ + Δ − 4)n = 4 .

This equality has solution only if n = 4 , δ = 2 , Δ = 3 , which characterizes a unique graph (obtained by inserting an edge into C_{4}). Thus C_{4} + e is the unique bicyclic graph with a zero critical value.

In the case of tricyclic graphs we arrive at the condition (δ +Δ−4)n = 8 which is satisfied by numerous graphs, all having n = 8 , δ = 1 , Δ = 4 or n = 8 , δ = 2 , Δ = 3 .

3.Trees

In the case of trees the minimum vertex degree is always δ = 1 . The only n-vertex tree with Δ = 2 is the path P_{n}, and this graph has already been analyzed in Example 1. Therefore we consider here trees for which Δ ≥ 3 . Thus δ + Δ ≥ 4 .

An n-vertex tree has n − 1 edges. Then, as special cases of Eqs. (5) and (6) we get

coeff_{0}(H) = n  ;  coeff_{0}(H_{1}) = 4(n − 1)

and therefore relation (16) in Lemma 3 is satisfied. This, together with Example 1, implies

Theorem 6a. Let G be an n-vertex tree. If G ≅ P_{n} , n ≥ 4 , then Eq.

(14) holds for near-zero values of λ. For all other n-vertex trees, n ≥ 3 , including P_{3} , Eq. (13) holds for near-zero values of λ.

If λ is sufficiently large, then the leading term of the polynomial H(G, λ) becomes d(G, D) λ^{D}, where d(G, D) is the number of pairs of vertices at greatest distance. If G is a tree, then all pairs of its vertices at greatest distance are of degree 1, and therefore for large λ the leading term of the polynomial H_{1}(G, λ) is 2 d(G, D) λ^{D}. Because for any n-vertex tree, n ≥ 3 , δ + Δ ≥ 3 , it immediately follows that all trees (including the paths) satisfy the condition (22) in Lemma 4. We thus arrive at

Theorem 6b. For all n-vertex trees, n ≥ 3 , Eq. (13) holds for sufficiently large values of λ.

4. Unicyclic Graphs

In this section we consider connected unicyclic graphs on n vertices. The cycle C_{n} is a regular graph of degree 2 and (for reasons explained above) will be disregarded. All other such graphs possess vertices of degree 1, and thus δ = 1 and Δ ≥ 3 . For connected unicyclic graphs, n = m, and therefore from Eqs. (5) and (6) we conclude that

coeff_{0}(H) = n  ;  coeff_{0}(H_{1}) = 4n .  (24)

We separately consider two cases: (1) Δ = 3 and (2) Δ > 3 .

Case 1: Δ = 3 Because of δ +Δ = 4 and relations (24), the equality (18) in Lemma 3 holds. Then, by Lemma 5 there follows that relation (20) in Lemma 3 is satisfied.

Case 2: Δ > 4 This time from Eqs. (24) we conclude

(δ + Δ) coeff_{0}(H) > 4n = coeff_{0}(H_{1}),

which means that relation (16) in Lemma 3 is obeyed. Summarizing the above consideration we have

Theorem 7a. Let G be an n-vertex connected unicyclic graph, different from the cycle C_{n}. If the greatest vertex degree in G is Δ = 3 , then Eq.

(14) holds for near-zero values of λ. If Δ ≥ 4 , then Eq. (13) holds for near-zero values of λ.

Let G be a connected unicyclic graph on n vertices, different from C_{n}, and let D be its diameter. Let x and y be two vertices of G whose distance is D. The following properties of these vertices are easily verified:

Claim 1. Either δ_{x} = 1 or δ_{y} = 1 , or both.

Claim 2. If δ_{x} = 1 , then δ_{y} ≤ 2 .

P r o o f. Any unicyclic graph G (different from C_{n}) consists of a cycle C to which some trees are attached.

Without loss of generality we assume that d(x, y) = D and δ_{x} ≤ δ_{y}. We prove the Claims 1 and 2 by showing that the assumptions (a) δ_{x} > 1 and (b) δ_{x} = 1 , δ_{y} > 2 lead to contradictions.

Case (a): δ_{x} > 1 .

If x belongs to a tree, attached to the cycle C, then (because its distance to y is maximal), it must be δ_{x} = 1 . Therefore, x must belong to the cycle C.

If x belongs to the cycle C and has degree greater than 2, then a tree is attached to C at vertex x. The vertex y cannot belong to this tree, because then the distance between y and any vertex of C, different than x, would be greater than D, a contradiction. If so, then the distance between y and any vertex of the tree attached to x is greater than D, a contradiction. Therefore it cannot be δ_{x} > 2 .

Therefore, if x belongs to the cycle C, its degree would have to be equal to 2. Because, δ_{y} ≥ δ_{x}, also the vertex y must belong to C.

If δ_{y} > 2 , then a tree is attached to y and the distance between x and any vertex of this tree is greater than D, a contradiction. If, however, δ_{y} = 2 , then on the cycle C there exists another pair of vertices x′, y′ at the same distance as x, y, such that a tree is attached to y′. The distance between x′ and any vertex of the tree attached to y′ would be greater than D, a contradiction.

Therefore, it cannot be δ_{x} > 1 .

Case (b): δ_{x} = 1 , δ_{y} > 2 .

If δ_{x} = 1 , then x belongs to a tree attached to C. If δ_{y} > 2 , then y must belong to C, and a tree is attached to C at y. Then the distance between x and at least one neighbor of y would be greater that D, a contradiction.

Therefore, if δ_{x} = 1 , then it cannot be δ_{y} > 2 . □

The above stated properties of maximum–distance vertex pairs imply δ_{x} + δ_{y} ≤ 3 , from which follows that

coeff_{D}(H_{1}) ≤ 3 d(G, D) .

On the other hand, because of δ + Δ ≥ 4 ,

(δ + Δ) coeff_{D}(H) ≥ 4 d(G, D)

which means that condition (22) in Lemma 4 is obeyed. This results in:

Theorem 7b. For all connected unicyclic n-vertex graphs, n ≥ 4 , different from the cycle C_{n}, Eq. (13) holds for sufficiently large values of λ.

5. Hexagonal Systems

Hexagonal systems form a class of graphs that is of certain importance in chemical applications; in chemical literature these graphs are often referred to as “benzenoid systems”. The basic properties of hexagonal systems are systematized in the book [11]; for their distance–based properties see the review [12] and elsewhere [10].

The basic structural features of hexagonal systems are best described by the following parameters: number of hexagons h and number of internal vertices n_{i}. Recall that n_{i} is equal to the number of vertices that simultaneously belong to three hexagons. Then the number of vertices and edges is equal to [11] n = 4h + 2 − n_{i} and m = 5h + 1 − n_{i}.

Hexagonal systems possess only vertices of degree 2 and 3. Their number is [11] n_{2} = 2h+4−n_{i} and n_{3} = 2h−2 , respectively. Taking these relations into account, and noting that

∑_{x∈V (G)}(δ_{x})^{2} = 4 n_{2} + 9 n_{3},

we arrive at the following special cases of Eqs. (5) and (6):

coeff_{0}(H) = 4h + 2 − n_{i}  ;  coeff_{1}(H) = 5h + 1 − n_{i}
coeff_{0}(H_{1}) = 20 h + 4 − 4 n_{i}  ;  coeff_{1}(H_{1}) = 26 h + 28 − 9 n_{i} .

The hexagonal systems with h = 1 coincides with the 6-vertex cycle, which is a regular graph. Therefore, in what follows we assume that h ≥ 2 . If so, then δ = 2 and Δ = 3 . Then, by direct calculation, we conclude that Eqs. (16) and (17) in Lemma 3 hold for n_{i} < 6 and n_{i} > 6 , respectively, and that for n_{i} = 6 the equality (18) is obeyed. In the case n_{i} = 6 we may apply Lemma 5. Based on these results and using Lemma 3 we can state

Theorem 8a. Let G be a hexagonal system with h hexagons, h ≥ 2 , and n_{i} internal vertices. If n_{i} ≤ 5 , then Eq. (13) holds for near-zero values of λ. If n_{i} ≥ 6 then Eq. (14) holds for near-zero values of λ.

In a hexagonal system any two vertices whose distance is maximal have degrees equal to 2. Therefore for any hexagonal system G whose diameter is D,

(δ + Δ) coeff_{D}(H) = 5 d(G, D) > 4 d(G, D) = coeff_{D}(H_{1}) .

Applying Lemma 4 we obtain

Theorem 8b. For all hexagonal systems, Eq. (13) holds for sufficiently large values of λ.

6. A Class of Graphs with Large Number of Edges

Let K_{n} be the complete graph on n vertices, and let e_{1}, e_{2}, …, e_{k} be independent edges of K_{n}. Let K_{n}(k) ≅ K_{n} − e_{1} − e_{2} − ⋯ − e_{k}.

Lemma 9. Let n ≥ 3 and 1 ≤ k < n/2 . For the graph G_{n}(k) the following holds: (a) If k < n/4 , then Eq. (14) holds for near-zero values of λ, there is a positive critical value, and Eq. (13) holds for sufficiently large λ. (b) If k = n/4, then there are two critical values: zero and 1. Eq. (14) holds for 0 < λ < 1 and Eq. (13) holds for λ > 1 . (c) If k > 4n, then Eq.

(13) holds for all non-negative values of λ.

P r o o f. Lemma 9 follows by direct calculation from

H(G_{n}(k), λ) = n + [\frac{n(n − 1)}{2} − k] λ + k λ^{2}

H_{1}(G_{n}(k), λ) = 4 [\frac{n(n − 1)}{2} − k]+[n(n − 1)^{2} − 2k(2n − 3)] λ + 2k(n − 2) λ^{2}

by taking into account that δ = n − 2 , Δ = n − 1 . □

REFERENCES

[1] I. G u t m a n, Some relations between distance–based polynomials of trees, Bull. Acad. Serbe Sci. Arts (Cl. Math. Natur.) 131 (2005) 1–7.

[2] H. H o s o y a, On some counting polynomials in chemistry, Discr. Appl. Math. 19 (1988) 239–257.

[3] I. G u t m a n, Some properties of the Wiener polynomial, Graph Theory Notes New York 25 (1993) 13–18.

[4] A. A. D o b r y n i n, Construction of graphs with a palindromic Wiener polynomial, Vychisl. Sistemy 151 (1994) 37–54 (in Russian).

[5] A. A. D o b r y n i n, Graphs with palindromic Wiener polynomials, Graph Theory Notes New York 27 (1994) 50–54.

[6] I. G u t m a n, E. E s t r a d a, O. I v a n c i u c, Some properties of the Wiener polynomial of trees, Graph Theory Notes New York 36 (1999) 7–13.

[7] I. G u t m a n, Hosoya polynomial and the distance of the total graph of a tree, Publ. Elektrotehn. Fak. (Beograd), Ser. Mat. 10 (1999) 53–58.

[8] G. C a p o r o s s i, A. A. D o b r y n i n, I. G u t m a n, P. H a n s e n, Trees with palindromic Hosoya polynomials, Graph Theory Notes New York 37 (1999) 10–16.

[9] D. S t e v a n o v i ć, Hosoya polynomial of composite graphs, Discr. Math. 235 (2001) 237–244.

[10] I. G u t m a n, S. K l a v ž a r, M. P e t k o v š e k, P. Ž i g e r t, On Hosoya polynomials of benzenoid graphs, MATCH Commun. Math. Comput. Chem. 43 (2001) 49–66.

[11] I. G u t m a n, S. J. C y v i n, Introduction to the Theory of Benzneoid Hydrocarbons, Springer–Verlag, Berlin, 1989.

[12] A. A. D o b r y n i n, I. G u t m a n, S. K l a v ž a r, P. Ž i g e r t, Wiener index of hexagonal systems, Acta Appl. Math. 72 (2002), 247–294.

Faculty of Science University of Kragujevac P. O. Box 60 34000 Kragujevac Serbia Department of Mathematics South China Normal University Guangzhou 510631 P. R. China