M Hudelson Vertex Topological Indices and Tree Expressions Generalizations of Continued Fractions

• Journal List
• HHS Author Manuscripts
• PMC2871707

J Math Chem. Author manuscript; available in PMC 2011 Jan 1.

Published in final edited form as:

PMCID: PMC2871707

NIHMSID: NIHMS187198

Vertex topological indices and tree expressions, generalizations of continued fractions

Matthew Hudelson

Department of Mathematics, Washington State University, P.O. Box 3113, Pullman, WA 99164, USA ude.usw@nosleduhm

Abstract

We expand on the work of Hosoya to describe a generalization of continued fractions called "tree expressions." Each rooted tree will be shown to correspond to a unique tree expression which can be evaluated as a rational number (not necessarily in lowest terms) whose numerator is equal to the Hosoya index of the entire tree and whose denominator is equal to the tree with the root deleted. In the development, we use Z(G) to define a natural candidate ζ(G, v) for a "vertex topological index" which is a value applied to each vertex of a graph, rather than a value assigned to the graph overall. Finally, we generalize the notion of tree expression to "labeled tree expressions" that correspond to labeled trees and show that such expressions can be evaluated as quotients of determinants of matrices that resemble adjacency matrices.

Keywords: Hosoya index, Topological index, Z-index

1 Introduction

In 1971, Hosoya inaugurated the study of topological descriptors of graphs in connection with chemical properties. In his initial work, he demonstrated that the number of ways to partition the set of atoms of an alkane into singletons or bonded pairs—a "matching" of the underlying graph in more modern terminology—is highly correlated to the boiling point of the alkane [3]. Hosoya dubbed the number of matchings Z(G) of the graph G its "topological index" Among Hosoya's early observations is the well-known fact that Z(P_n ) = F _n+1, the (n + 1)st Fibonacci number [4]. Hosoya was able to generalize this to computing Z(G) where G is a caterpillar by using continuants of continued fractions [5–7]. Hosoya and Gutman's most recent paper [8] gives details on relating Z(G) of an underlying caterpillar to the number K of Kekulé structures. Hosoya and Gutman's paper includes an extensive list of other recent applications of Z(G) which we include here as well [2,9–12]. We also note that Hosoya's use of continuants to enumerate Z(G) for caterpillars exactly mirrors tilings of paths by dominos and stacks of squares detailed by Benjamin and Quinn [1]. Insights such as these that connect continued fractions to enumeration problems have led to the results contained in this paper.

For our note, we begin with the observation (made by Hosoya himself and many others) that Hosoya's index can be computed recursively on a graph G by letting u by any vertex and

Z ( G ) = Z ( G − u ) + ∑ v ∈ N ( u ) Z ( ( G − u ) − v )

(1)

where N (u) is the set of vertices adjacent to u. Of course to supply initial conditions for the recurrence, we have Z(G) = 1 if G is a graph with no edges; this is consistent with the definition of Z as the number of matchings of G. We then perform the simple step of dividing both sides of Eq. 1 by Z(G − u), obtaining

Z ( G ) Z ( G − u ) = 1 + ∑ v ∈ N ( u ) Z ( ( G − u ) − v ) Z ( G − u ) .

We define the "vertex topological index"

and obtain at once a recurrence for ζ:

ζ ( G , u ) = 1 + ∑ v ∈ N ( u ) 1 ζ ( G − u , v )

(2)

with initial condition ζ(G, u) = 1 if u has no neighbors in G.

Hosoya [8] observes that if G has several components C ₁, C ₂,…,C_k then

Z(G) =Z(C ₁)Z(C ₂) ⋯Z(C _k ).

(3)

This is easy to see as the matchings are independent among the components. From this, we see that if C ₁ is the component that contains u, then

ζ ( G , u ) = Z ( G ) Z ( G − u ) = Z ( C 1 ) Z ( C 2 ) ⋯ Z ( C k ) Z ( C 1 − u ) Z ( C 2 ) ⋯ Z ( C k ) = Z ( C 1 ) Z ( C 1 − u ) = ζ ( C 1 , u ) .

(4)

2 Ordinary tree expressions

We now restrict our attention to the case where T is a tree with root r. Letting r ₁, r ₂, …, r_k be the neighbors of r, by deleting r from T, we would obtain a forest each of whose components would be a rooted tree T_i with root r_i . At once, by applying Eqs. 2 and 4 in this situation, we have

Theorem 1

Given a tree T with root r as well as T_i and r_i as defined above,

The initial condition for this recurrence is the single-vertex tree T = r and we already have ζ(r, r) = 1. Alternatively, we could note that r would have no neighbors and the sum in Eq. 4 would be empty.

Any rooted tree (T, r) can now be associated with a "tree expression" τ (T, r) as generated by the conclusion of Theorem 1. For instance, the tree expression for a five-vertex path P ₅ rooted at the central vertex v ₃ would be

More formally, we define a "tree expression" τ and associated rooted tree by the following recursive recipe:

1. The value 1 is a tree expression associated with the single-vertex tree, i.e., τ(r, r) = 1.

2. If τ _i , 1 ≤ i ≤ k are tree expressions then so is

   τ = 1 + ∑ i = 1 k 1 τ i

   . Given that we have associated each rooted tree (T_i, r_i ) with τ _i , we associate the rooted tree (T, r) with τ.

We will use the notation τ(T, r) to represent the tree expression associated with the rooted tree (T, r). Armed with our definition and Theorem 1, we immediately have

Corollary 1

Given a rooted tree (T, r), τ(T, r) = ζ (T, r).

We would like to conclude that the numerator of τ = τ(T, r) yields Z(T), but it's entirely possible that we do not obtain this value if τ is reduced to lowest terms. For instance, if we calculate τ(P ₅, v ₃) we obtain the value 2 which does not convey the true value of Z(P ₅) = 8 or Z(P ₅ − v ₃) = 4. On the other hand, we can circumvent this difficulty simply by not reducing to lowest terms at any time, as we show in the next theorem.

Theorem 2

If (T, r) is a rooted tree with rooted trees (T_i, r_i ) defined as before and if each τ(T_i, r_i ) = a_i/b_i has been evaluated so that a_i = Z(T_i ) and b_i = Z(T_i − r_i ) then evaluating τ(T, r) = a/b using the "product common denominator" as opposed to the lowest common denominator yields a = Z(T) and b = Z(T − r).

Proof

We proceed by (strong) mathematical induction on the number of applications of Eq. 5 necessary to complete the evaluation of ζ(T, r). If this number is zero, then there are no components at all to T − r, i.e., T = r is a single vertex. But then τ(T, r) = 1 = 1/1 and Z(T) = 1 and Z(T − r) = 1 which verifies the basis step. For the inductive step, we assume a_i = Z(T_i ) and b_i = Z(T_i − r_i ) as in the hypothesis. Now, when faced with evaluating τ(T, r) = a/b, we have

a b = 1 + ∑ i = 1 k 1 τ ( T i , r i ) = 1 + ∑ i = 1 k b i a i = a 1 a 2 a 3 ⋯ a k + b 1 a 2 a 3 ⋯ a k + a 1 b 2 a 3 ⋯ a k + ⋯ a 1 a 2 a 3 ⋯ b k a 1 a 2 a 3 ⋯ a k

We now observe that

b = a 1 a 2 ⋯ a k = Z ( T 1 ) Z ( T 2 ) ⋯ Z ( T k ) = Z ( T − r )

which follows from Eq. 3. Finally, we have from Corollary 2 that

which, together with b = Z(T − r), implies a = Z(T) as desired.

We can see this in action in our example

τ ( P 5 , v 3 ) = 1 + 1 1 + 1 1 + 1 1 + 1 1 = 1 + 1 2 + 1 2 = 4 4 + 2 4 + 2 4 = 8 4

We have seen how to go from rooted trees to tree expressions. The reverse direction of constructing a tree from a given tree expression has an intriguing graphical interpretation. Suppose we have a tree expression τ = 1 + ∑ i 1 τ i. The initial "1" in the expression 1 + ∑ i 1 τ i will be called the "leading 1"; each of the τ _i expressions will in turn have leading 1s. We construct the rooted tree (T, r) recursively. If τ = 1, we declare T to be the single vertex r. Otherwise, we assume that each tree expression τ _i has led to the construction of the rooted tree (T_i, r_i ). The leading 1 of τ is declared to be the root r and we join r to each of the vertices r_i , forming the tree T. The construction of (T, r) from τ is precisely the "unraveling" of the construction of τ from (T, r) and so we have a one-to-one correspondence between rooted trees and tree expressions.

One means of picturing the construction of (T, r) from τ is simply to circle all of the leading 1s and then joining any leading 1 to the leading 1s of expressions at the 'next level under the same fraction bar.' This is demonstrated in Fig. 1.

The rooted graph (T, v) produced from the leading 1s of τ

3 Labeled tree expressions

We can generalize tree expressions to be applied to trees whose vertices are assigned numerical labels by replacing the 1s that appear in denominators with the labels. More specifically, suppose (T, v ₁) is a rooted tree with vertices v ₀, v ₁, …, v_n and vertex i has label x_i . We then define its labeled tree expression λ(T, v ₀) by the recursive recipe

1. If the vertex set of T is {v ₀}, then λ(T, v ₀) = x ₀.

2. If the root is adjacent to vertices v _{i 1} , v _{i 2} , …, v_ik and that C_j is the component of T − v ₀ that contains v_ij , then λ(T, v ₀) = x ₀ + ∑ _j 1/λ(C_j , v_ij ).

In the case of a path P = v ₀ v ₁ … v_n rooted at v ₀, we obtain as its labeled tree expression the continued fraction

λ ( P , v 0 ) = x 0 + 1 x 1 + 1 x 2 + 1 ⋱ ⋱ x n − 1 + 1 x n

Hosoya and Gutman [8] point out that

λ ( P , v 0 ) = det M ( x 0 , x 1 , x 2 , … , x n ) det M ( x 1 , x 2 , … , x n )

where

M ( d 1 , d 2 , d 3 , … , d k ) = ( d 1 1 − 1 d 2 1 − 1 d 3 1 − 1 d 4 ⋱ d k − 1 1 − 1 d k )

denotes the k × k tridiagonal matrix whose diagonal entries are d ₁, …, d_k , whose entries just above the diagonal are all 1 and whose entries just below the diagonal are all − 1.

We show that in fact this observation can be generalized to labeled tree expressions. If G is a labeled graph where vertex v_r is assigned label x_r , we define the matrix B(G) by the formula

B ( G ) ij = { x i , i = j ; 1 , i < j , v i adjacent to v j ; − 1 , i > j , v i adjacent to v j ; 0 , i ≠ j , v i not adjacent to v j .

In short, this matrix has the vertex labels along the diagonal, takes on the values of A(G), the adjacency matrix of G above the diagonal and takes on the negatives of the values of A(G) below the diagonal.

As an example of this more general situation, if (T, v ₀) is the rooted tree that produces the tree expression τ in Fig. 1,

τ ( T , v 0 ) = 1 + 1 1 + 1 1 + 1 1 + 1 1 + 1 1 + 1 1 + 1 1 + 1 1 + 1 1 ,

then

λ ( T , v 0 ) = x 0 + 1 x 1 + 1 x 2 + 1 x 3 + 1 x 4 + 1 x 5 + 1 x 6 + 1 x 7 + 1 x 8 + 1 x 9 ,

and (suppressing the zero elements),

B ( T ) = ( x 0 1 1 1 1 − 1 x 1 − 1 x 2 1 − 1 x 3 − 1 x 4 1 − 1 x 5 − 1 x 6 1 1 − 1 x 7 − 1 x 8 1 − 1 x 9 )

We make some preliminary observations that will assist in the proof of our next main result that generalizes the Hosoya and Gutman observation, linking λ(T, r) and the determinant of B-matrices. Given a tree T, we observe that if we expand the determinant of B(T) by the usual signed permutation sum

det B ( T ) = ∑ σ ∈ S n ( − 1 ) sgn ( σ ) ∏ i = 1 n ( B ( T ) ) i , σ ( i )

then an x_j value occurs in a term if and only if σ(j) = j. Also, since T has no cycles of length 3 or more, no permutation with a cycle of length 3 or more can make a nonzero contribution to det B(T). Thus, if B(T) _j,k is in any term ∏ i = 1 n ( B ( T ) ) i , σ ( i ) that makes a nonzero contribution to det B(T) then so is B(T) _{k, j} .

We also note that if G − v has components C ₁, C ₂, …, C_k then there is a permutation matrix P such that P ⁻¹ B(G − v)P is a block diagonal matrix, each block being of the form B(C_i ). This is tantamount to renumbering the vertices so that for each 1 ≤ i ≤ k − 1, the vertices of component C_i have numbers below those of C _i+1. Thus, det B ( G − v ) = ∏ i = 1 k det B ( C i ).

We are now ready to prove our result.

Theorem 3

If (T, r) is a labeled tree then

where B(T − r) is the specific matrix obtained by removing the row and column corresponding to r. We adopt the convention that det B(T − r) = 1 to make sense of the case when T is the graph with the single vertex r.

Proof

The proof is by (strong) induction on the number of vertices n in T. The basis step is when T has the single vertex r with label x. In this case, λ(T, r) = x and B(T) = [x] by definition. With the convention that det B(T − r) = 1, the basis step is easily verified. For the inductive step, suppose the vertices are v ₀ = r, v ₁, …, v _{n − 1}. Suppose further that v_i is labeled x_i and suppose r = v ₀ is adjacent to vertices v _{i 1} , v _{i 2} , …, v_ik where v_i is the root of component C_i of the graph T − r. If we expand det B(T) along "row 0", corresponding to r = v ₀, we obtain

det B ( T ) = x 0 det B ( T − r ) + ∑ j det B ( T − r − v i j ) .

The second expression arises from each occurrence of a B(T)_0,ij = 1. From our preliminary observations, B(T) _{ij ,0} = −1 must also appear in the term. These two terms form a transposition and so contribute a second factor of −1 to the product forming this term in the determinant; the remaining factor is det B(T − r − v_ij ).

We now divide each side of our formula for det B(T) by det B(T − r), obtaining

det B ( T ) det B ( T − r ) = x 0 + ∑ j det B ( T − r − v i j ) det B ( T − r ) .

Finally, if C_j is the component of T − r that contains v_ij then by our preliminary observations,

det B ( T − r − v i j ) det B ( T − r ) = det B ( C j − v i j ) det B ( C j ) = 1 λ ( C j , v i j )

by the inductive hypothesis. Therefore,

det B ( T ) det B ( T − r ) = x 0 + ∑ j 1 λ ( C j , v i j ) = λ ( T , r )

by the recursive definition of λ(T, r) and we are done.

We finish with the following result that links det B(G) to matchings in the more general case when G is a graph with no even cycles.

Theorem 4

Let G be a graph with no even cycles and let P(G) = det B(G), treated as a polynomial in the x_i. Then the coefficient of x _{i 1} x _{i 2} … x _{i k} of P(G) enumerates the perfect matchings of the graph G′ induced by the vertices whose indices are not in {i ₁, i ₂, …, i_k }.

Proof

Again, we analyze the determinant by means of the usual formula involving permutations σ ∈ S_n :

P ( G ) = ∑ σ ∈ S n ( − 1 ) sgn ( σ ) ∏ i = 1 n ( B ( G ) ) i , σ ( i ) .

(6)

The only permutations that contribute to the desired coefficient are those that have each of i ₁, i ₂, …, i_k as their only fixed points. Let σ be such a permutation and suppose that σ has a cycle of length at least 3. Let C = (a ₁, a ₂, …, a_q ) be the cycle of any length at least 3 with the lowest entry such that each (B(G)) _{a i ,a i+1} along with (B(G)) _{a q ,a 1} is either 1 or −1. Since G has no even cycles, q must be odd.

Since q is odd, the number of the values (B(G)) _{ai ,a i+1} or (B(G)) _{aq ,a 1} that equal −1 must have the opposite parity of the number of values that equal 1. If we let σ′ be the permutation where C is reversed but otherwise σ′ (i) = σ (i), then we are interested in the values (B(G)) _{a i+1,ai} along with (B(G)) _{a 1,aq} . Here, the parities of the number of −1 values and the number of 1 values are reversed. We conclude that the contributions of σ and σ′ to P(G) eliminate each other. Such permutations come in pairs (thanks to the definition of C) and so the only permutations that can contribute to the desired coefficient without being cancelled by another permutation are those that fix i ₁, i ₂, …, i_k and transpose all of the remaining entries in pairs. Each transposition (a, b), a < b, contributes to the product in Eq. 1 one factor of −1 in (−1)^sign(σ), a factor of 1 from (B(G)) _a,b , and a factor of −1 from (B(G)) _b,a . In summary, each (B(G)) _ij,ij = x_ij and each transposition contributes two factors of −1 to the product, and so the product (−1)^sign(σ) ∏ i = 1 n ( B ( G ) ) i , σ ( i ) = x i 1 x i 2 … x i k. Finally, each transposition corresponds to an edge in G′ and so σ corresponds to a perfect matching of G′, which yields the result.

We close by noting the following corollaries.

Corollary 2

Given a graph G with no even cycles (this includes trees), the Hosoya index Z(G) is P(G)(1, 1, …, 1) and the number of perfect matchings is P(G) (0, 0, …, 0).

Corollary 3

Given a graph G with no even cycles and a vertex v,

ζ ( G , v ) = P ( G ) ( 1 , 1 , … , 1 ) P ( G − v ) ( 1 , 1 , … , 1 ) .

For such graphs, this provides a polynomial-time formula for computing ζ(G, v).

Acknowledgments

The author wishes to acknowledge the contributions of the anonymous referees for pointing out many improvements to this paper, and especially for referring the author to the paper by Hosoya and Gutman that led to the results in the final section. Funding for this effort was provided by NIH grant number 9-R01-GM084546-11.

References

1. Benjamin A, Quinn J. Proofs that Really Count. The Art of Combinatorial Proof. Washington, DC: Mathematical Association of America; 2003. [Google Scholar]

2. Cash GG. J. Math. Chem. 2005;37:117–125. [Google Scholar]

3. Hosoya H. Bull. Chem. Soc. Jpn. 1971;44:2332–2339. [Google Scholar]

4. Hosoya H. Fibonacci Q. 1973;11:255–266. [Google Scholar]

5. Hosoya H. Continuant, caterpillar, and topological index Z. Fastest algorithm for degrading a continued fraction. Nat. Sci. Rep. Ochanomizu Univ. 2007;58(1):15–28. [Google Scholar]

6. Hosoya H. Important mathematical structures of the topological index Z for tree graphs. J. Chem. Inf. Model. 2007;47:744–750. [PubMed] [Google Scholar]

7. Hosoya H. Continuant, caterpillar, and topological index Z. Novel identities involving Fibonacci, Lucas, and generalized Fibonacci numbers. Nat. Sci. Rep. Ochanomizu Univ. 2008;58(2):11–20. [Google Scholar]

8. Hosoya H, Gutman I. Kekulé structures of hexagonal chains—some unusual connections. J. Math. Chem. 2008;44:559–568. [Google Scholar]

9. Liu H, Yan X, Yan Z, Zhou MJ. MATCH Commun. Math. Comput. Chem. 2007;57:235. [Google Scholar]

10. Pan X, Yang C, Zhou MJ. MATCH Commun. Math. Comput. Chem. 2007;57:371. [Google Scholar]

11. Wagner SG. MATCH Commun. Math. Comput. Chem. 2007;57:221. [Google Scholar]

12. Yu A, Lv X. The Merrifield–Simmons indices and Hosoya indices of trees with k pendant vertices. J. Math. Chem. 2007;41:33–43. [Google Scholar]

hilbertaleirt.blogspot.com

Source: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2871707/

Share this post