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

SOME RELATIONS BETWEEN DISTANCE–BASED POLYNOMIALS OF TREES

I. GUTMAN

(Presented at the 6th Meeting, held on September 24, 2004)

A b s t r a c t. The Hosoya polynomial H(G, λ) of a graph G has the property that its first derivative at λ = 1 is equal to the Wiener index. Sometime ago two distance-based graph invariants were studied – the Schultz index S and its modification S^{∗}. We construct distance–based graph polynomials H_{1}(G, λ) and H_{2}(G, λ) , such that their first derivatives at λ = 1 are, respectively, equal to S and S^{∗}. In case of trees, H_{1}(G, λ) and H_{2}(G, λ) are related with H(G, λ) .

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

Schultz index

1. Introduction

In this work we study some distance–based graph invariants and polynomials, and find relations between them. Let G be a connected graph, V (G) its vertex set, n the number of its vertices, and m the number of its edges.

Let x and y be vertices of the graph G. The distance d(x, y) between them (equal to the length of the shortest path connecting them) is denoted by d(x, y) . If x = y, then d(x, y) = 0 . The number of pairs of vertices of G that are at distance k is denoted by d(G, k) . In particular, d(G, 0) = n,

d(G, 1) = m, and ∑_{k≥0} d(G, k) = \binom{n}{2} + n = n(n + 1)/2 .

The degree δ_{x} of the vertex x is the number of first neighbors of this vertex.

A much studied distance–based graph invariant is the Wiener index, defined as

W = W (G) = ∑_{{x,y}⊆V (G)} d(x, y)  (1)

which also can be written as

W = W (G) = ∑_{k≥0} k d(G, k) .  (2)

For details on the mathematical properties of the Wiener index see the reviews [1, 2].

Hosoya [3] introduced a distance–based graph polynomial

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

nowadays called the “Hosoya polynomial”. A less usual, yet equivalent, form in which this polynomial can be written is

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

As easily seen from Eqs. (2) and (3) or from (1) and (4), the first derivative of the Hosoya polynomial at λ = 1 is equal to the Wiener index.

In connection with certain investigations in mathematical chemistry, Schultz [4] considered a graph invariant that he called “molecular topological index” and whose essential part is the Schultz index S,

S = S(G) = ∑_{{x,y}⊆V (G)}(δ_{x} + δ_{y}) d(x, y) .  (5)

The Schultz index attracted some attention after it was discovered that in the case of trees it is closely related to the Wiener index [5]:

Theorem 1. If G is a tree on n vertices, then its Schultz and Wiener indices are related as

S(G) = 4 W (G) − n(n − 1) .  (6)

Motivated by Eqs. (5) and (6), the present author [6] examined an invariant S^{∗},

S^{∗} = S^{∗}(G) = ∑_{{x,y}⊆V (G)} δ_{x} δ_{y} d(x, y)  (7)

which here we refer to as the modified Schultz index. A result analogous to Theorem 1 applies [6]:

Theorem 2. If G is a tree on n vertices, then its modified Schultz and Wiener indices are related as

S^{∗}(G) = 4 W (G) − (n − 1)(2n − 1) .  (8)

2. Graph Polynomials Related to the Schultz and Modified Schultz Indices

Bearing in mind Eqs. (4), (5), and (7), it is easy to construct graph polynomials having the property that their first derivatives at λ = 1 are equal to the Schultz and modified Schultz indices. These polynomials are

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

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

In view of Eqs. (6) and (8) one may ask if there exist relations between the polynomials H_{1} and H_{2} and the Hosoya polynomial, in particular in the case of trees. The answer to this question is affirmative, and we have

Theorem 3. If G is a tree on n vertices, then the polynomials H_{1}(G, λ) and H(G, λ) are related as

H_{1}(G, λ) = 2 (1 + \frac{1}{λ}) H(G, λ) − 2 (1 + \frac{n}{λ}) .  (11)

Theorem 4. If G is a tree on n vertices, then the polynomials H_{2}(G, λ) and H(G, λ) are related as

H_{2}(G, λ) = (1 + \frac{1}{λ})^{2} H(G, λ) − (1 + \frac{1}{λ}) (2 + \frac{1}{λ}) n

+ (1 + \frac{1}{λ}) + \frac{1}{2} ∑_{x∈V (G)}(δ_{x})^{2} .  (12)

3. Proof of Theorem 3

Lemma 5. If G is a tree, then

∑_{x≠y}(δ_{x} + δ_{y} − 2) λ^{d(x,y)+1} = 2 ∑_{k≥2} d(G, k) λ^{k},  (13)

where ∑_{x≠y} indicates summation over all pairs of different vertices x, y of G.

P r o o f. The sum

∑_{x≠y}(δ_{y} − 1) λ^{d(x,y)+1}

can be viewed as going over all pairs of vertices x, z of the tree G, where z is adjacent to y and is at greater distance from x than y. Because G is a tree, there exist exactly δ_{y} − 1 such vertices, and their distances to x are equal to d(x, y) + 1 . In other words, the above sum is equal to the sum of the terms λ^{d(x,z)} over all pairs of vertices of the tree G whose distance is 2 or greater, i. e.,

∑_{x≠y}(δ_{y} − 1) λ^{d(x,y)+1} = ∑_{k≥2} d(G, k) λ^{k} .  (14)

By the very same argument,

∑_{x≠y}(δ_{x} − 1) λ^{d(x,y)+1} = ∑_{k≥2} d(G, k) λ^{k} .  (15)

By adding (14) and (15) we obtain (13). □

P r o o f of Theorem 3. Bearing in mind Lemma 5, we rewrite the right–hand side of (9) as

H_{1}(G, λ) = ∑_{x≠y}(δ_{x} + δ_{y} − 2) λ^{d(x,y)} + ∑_{x=y}(δ_{x} + δ_{y} − 2) λ^{d(x,y)}

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

Now, by Lemma 5,

∑_{x≠y}(δ_{x} + δ_{y} − 2) λ^{d(x,y)} = \frac{1}{λ} ∑_{k≥2} d(G, k) λ^{k} .

If x = y then d(x, y) = 0 and the second term on the right–hand side of (16) is equal to

∑_{x∈V (G)}(2 δ_{x} − 2) = 4m − 2n = 4(n − 1) − 2n = 2n − 4 .

By (4), the third term on the right–hand side of (16) is just twice the Hosoya polynomial.

We thus get

H_{1}(G, λ) = \frac{1}{λ} ∑_{k≥2} d(G, k) λ^{k} + (2n − 4) + 2 H(G, λ) .

Taking into account that

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

we directly arrive at formula (11). □

Formula (6) can now be obtained as a simple corollary of Theorem 3. Indeed, one just has to compute the first derivative of (11), set λ = 1 , and use the relations H(G, 1) = n(n + 1) and H′(G, 1) = W .

4. Proof of Theorem 4

Lemma 6. If G is a tree, then

∑_{x≠y}(δ_{x} − 1)(δ_{y} − 1) λ^{d(x,y)+2} = ∑_{k≥3} d(G, k) λ^{k} .  (17)

P r o o f. The sum

∑_{x≠y}(δ_{x} − 1)(δ_{y} − 1) λ^{d(x,y)+2}

can be viewed as embracing all pairs of vertices z, z′ of the tree G, where z is adjacent to x and is at greater distance from y than x, and z′ is adjacent to y and is at greater distance from x than y. Because G is a tree, there exist exactly δ_{x} − 1 vertices z and δ_{y} − 1 vertices z′, and thus a total of (δ_{x} − 1)(δ_{y} − 1) vertex pairs z, z′. The distance of each such vertex pair is d(x, y) + 2 . This implies that the above sum is equal to the sum of the terms λ^{d(z,z′)} over all pairs of vertices of the tree G whose distance is 3 or greater, i. e., implies Eq. (17)

P r o o f of Theorem 4. In view of Lemma 6, we rewrite the right-hand side of (10) as

H_{2}(G, λ) = ∑_{x≠y}(δ_{x} − 1)(δ_{y} − 1) λ^{d(x,y)} + ∑_{x=y}(δ_{x} − 1)(δ_{y} − 1) λ^{d(x,y)}

+ ∑_{{x,y}⊆V (G)}(δ_{x} + δ_{y}) λ^{d(x,y)} − ∑_{{x,y}⊆V (G)} λ^{d(x,y)} .  (18)

Then by Lemma 6,

∑_{x≠y}(δ_{x} − 1)(δ_{y} − 1) λ^{d(x,y)} = \frac{1}{λ^{2}} ∑_{k≥3} d(G, k) λ^{k},

whereas the third and fourth terms on the right–hand side of (18) are just the polynomials H_{1}(G, λ) and H(G, λ) , respectively. The second term in (18) is simply

∑_{x∈V (G)}(δ_{x} − 1)^{2} = ∑_{x∈V (G)}(δ_{x})^{2} − 4m + n = ∑_{x∈V (G)}(δ_{x})^{2} − 3n + 4 .

Therefore,

H_{2}(G, λ) = \frac{1}{λ^{2}} ∑_{k≥3} d(G, k) λ^{k} + ∑_{x∈V (G)}(δ_{x})^{2} − 3n + 4 + H_{1}(G, λ) − H(G, λ) .

By taking into account that

∑_{k≥3} d(G, k) λ^{k} = H(G, λ) − n − (n − 1) λ − d(G, 2) λ^{2},

recalling that in the case of trees [7]

d(G, 2) = \frac{1}{2} ∑_{x∈V (G)}(δ_{x})^{2} − (n − 1),

and using the expression (11) for H_{1}(G, λ) , we arrive at Eq. (12), that is at Theorem 4. □

Formula (8) becomes now a corollary of Theorem 4. It is obtained by setting λ = 1 into the first derivative of (12), using the relations (2) and (7), as well as H(G, 1) = n(n + 1) and H′(G, 1) = W .

REFERENCES

[1] A. A. D o b r y n i n, R. E n t r i n g e r, I. G u t m a n, Wiener index of trees: theory and applications, Acta Appl. Math. 66 (2001), 211–249.

[2] 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.

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

[4] H. P. S c h u l t z, Topological organic chemistry. 1. Graph theory and topological indices of alkanes, J. Chem. Inf. Comput. Sci. 29, (1989) 227–228.

[5] D. J. K l e i n, Z. M i h a l i ć, D. P l a v š i ć, N. T r i n a j s t i ć, Molecular topological index: A relation with the Wiener index, J. Chem. Inf. Comput. Sci. 32, (1992) 304–305.

[6] I. G u t m a n, Selected properties of the Schultz molecular topological index, J. Chem. Inf. Comput. Sci. 34, (1994) 1087–1089.

[7] I. G u t m a n, K. C. D a s, The first Zagreb index 30 years after, MATCH Commun. Math. Comput. Chem. 50, (2004) 83–92.

Faculty of Science University of Kragujevac P. O. Box 60 34000 Kragujevac Serbia and Montenegro