PMCCPMCCPMCC

Search tips
Search criteria 

Advanced

 
Logo of nihpaAbout Author manuscriptsSubmit a manuscriptHHS Public Access; Author Manuscript; Accepted for publication in peer reviewed journal;
 
J Math Chem. Author manuscript; available in PMC 2011 January 1.
Published in final edited form as:
J Math Chem. 2010 January; 47(1): 219–228.
PMCID: PMC2871707
NIHMSID: NIHMS187198

Vertex topological indices and tree expressions, generalizations of continued fractions

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(Pn) = Fn+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 [57]. 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,912]. 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(Gu)+vN(u)Z((Gu)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(Gu), obtaining

Z(G)Z(Gu)=1+vN(u)Z((Gu)v)Z(Gu).

We define the “vertex topological index”

ζ(G,v)=Z(G)Z(Gu)

and obtain at once a recurrence for ζ:

ζ(G,u)=1+vN(u)1ζ(Gu,v)
(2)

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

Hosoya [8] observes that if G has several components C1, C2,…,Ck then

Z(G)=Z(C1)Z(C2)Z(Ck).
(3)

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

ζ(G,u)=Z(G)Z(Gu)=Z(C1)Z(C2)Z(Ck)Z(C1u)Z(C2)Z(Ck)=Z(C1)Z(C1u)=ζ(C1,u).
(4)

2 Ordinary tree expressions

We now restrict our attention to the case where T is a tree with root r. Letting r1, r2, …, rk be the neighbors of r, by deleting r from T, we would obtain a forest each of whose components would be a rooted tree Ti with root ri. 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 Ti and ri as defined above,

ζ(T,r)=1+i1ζ(Ti,ri).
(5)

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 P5 rooted at the central vertex v3 would be

τ(P5,v3)=1+11+11+11+11.

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 ≤ ik are tree expressions then so is τ=1+i=1k1τi. Given that we have associated each rooted tree (Ti, ri) 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 τ(P5, v3) we obtain the value 2 which does not convey the true value of Z(P5) = 8 or Z(P5v3) = 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 (Ti, ri) defined as before and if each τ(Ti, ri) = ai/bi has been evaluated so that ai = Z(Ti) and bi = Z(Tiri) 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(Tr).

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 Tr, i.e., T = r is a single vertex. But then τ(T, r) = 1 = 1/1 and Z(T) = 1 and Z(Tr) = 1 which verifies the basis step. For the inductive step, we assume ai = Z(Ti) and bi = Z(Tiri) as in the hypothesis. Now, when faced with evaluating τ(T, r) = a/b, we have

ab=1+i=1k1τ(Ti,ri)=1+i=1kbiai=a1a2a3ak+b1a2a3ak+a1b2a3ak+a1a2a3bka1a2a3ak

We now observe that

b=a1a2ak=Z(T1)Z(T2)Z(Tk)=Z(Tr)

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

ab=ζ(T,r)=Z(T)Z(Tr)

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

We can see this in action in our example

τ(P5,v3)=1+11+11+11+11=1+12+12=44+24+24=84

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+i1τi. The initial “1” in the expression 1+i1τ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 (Ti, ri). The leading 1 of τ is declared to be the root r and we join r to each of the vertices ri, 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.

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, v1) is a rooted tree with vertices v0, v1, …, vn and vertex i has label xi. We then define its labeled tree expression λ(T, v0) by the recursive recipe

  1. If the vertex set of T is {v0}, then λ(T, v0) = x0.
  2. If the root is adjacent to vertices vi1, vi2, …, vik and that Cj is the component of Tv0 that contains vij, then λ(T, v0) = x0 + ∑j 1/λ(Cj, vij).

In the case of a path P = v0v1vn rooted at v0, we obtain as its labeled tree expression the continued fraction

λ(P,v0)=x0+1x1+1x2+1xn1+1xn

Hosoya and Gutman [8] point out that

λ(P,v0)=detM(x0,x1,x2,,xn)detM(x1,x2,,xn)

where

M(d1,d2,d3,,dk)=(d111d211d311d4dk111dk)

denotes the k × k tridiagonal matrix whose diagonal entries are d1, …, dk, 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 vr is assigned label xr, we define the matrix B(G) by the formula

B(G)ij={xi,i=j;1,i<j,viadjacent tovj;1,i>j,viadjacent tovj;0,ij,vinot adjacent tovj.

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, v0) is the rooted tree that produces the tree expression τ in Fig. 1,

τ(T,v0)=1+11+11+11+11+11+11+11+11+11,

then

λ(T,v0)=x0+1x1+1x2+1x3+1x4+1x5+1x6+1x7+1x8+1x9,

and (suppressing the zero elements),

B(T)=(x011111x11x211x31x411x51x6111x71x811x9)

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

detB(T)=σSn(1)sgn(σ)i=1n(B(T))i,σ(i)

then an xj 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=1n(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 Gv has components C1, C2, …, Ck then there is a permutation matrix P such that P−1 B(Gv)P is a block diagonal matrix, each block being of the form B(Ci). This is tantamount to renumbering the vertices so that for each 1 ≤ ik − 1, the vertices of component Ci have numbers below those of Ci+1. Thus, det B(Gv)=i=1kdetB(Ci).

We are now ready to prove our result.

Theorem 3

If (T, r) is a labeled tree then

λ(T,r)=detB(T)detB(Tr)

where B(Tr) is the specific matrix obtained by removing the row and column corresponding to r. We adopt the convention that det B(Tr) = 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(Tr) = 1, the basis step is easily verified. For the inductive step, suppose the vertices are v0 = r, v1, …, vn − 1. Suppose further that vi is labeled xi and suppose r = v0 is adjacent to vertices vi1, vi2, …, vik where vi is the root of component Ci of the graph Tr. If we expand det B(T) along “row 0”, corresponding to r = v0, we obtain

detB(T)=x0detB(Tr)+jdetB(Trvij).

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(Trvij).

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

detB(T)detB(Tr)=x0+jdetB(Trvij)detB(Tr).

Finally, if Cj is the component of Tr that contains vij then by our preliminary observations,

detB(Trvij)detB(Tr)=detB(Cjvij)detB(Cj)=1λ(Cj,vij)

by the inductive hypothesis. Therefore,

detB(T)detB(Tr)=x0+j1λ(Cj,vij)=λ(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 xi. Then the coefficient of xi1xi2xik of P(G) enumerates the perfect matchings of the graph G′ induced by the vertices whose indices are not in {i1, i2, …, ik}.

Proof

Again, we analyze the determinant by means of the usual formula involving permutations σ [set membership] Sn:

P(G)=σSn(1)sgn(σ)i=1n(B(G))i,σ(i).
(6)

The only permutations that contribute to the desired coefficient are those that have each of i1, i2, …, ik as their only fixed points. Let σ be such a permutation and suppose that σ has a cycle of length at least 3. Let C = (a1, a2, …, aq) be the cycle of any length at least 3 with the lowest entry such that each (B(G))ai,ai+1 along with (B(G))aq,a1 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,ai+1 or (B(G))aq,a1 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))ai+1,ai along with (B(G))a1,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 i1, i2, …, ik 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 = xij and each transposition contributes two factors of −1 to the product, and so the product (−1)sign(σ) i=1n(B(G))i,σ(i)=xi1xi2xik. 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(Gv)(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.
2. Cash GG. J. Math. Chem. 2005;37:117–125.
3. Hosoya H. Bull. Chem. Soc. Jpn. 1971;44:2332–2339.
4. Hosoya H. Fibonacci Q. 1973;11:255–266.
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.
6. Hosoya H. Important mathematical structures of the topological index Z for tree graphs. J. Chem. Inf. Model. 2007;47:744–750. [PubMed]
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.
8. Hosoya H, Gutman I. Kekulé structures of hexagonal chains—some unusual connections. J. Math. Chem. 2008;44:559–568.
9. Liu H, Yan X, Yan Z, Zhou MJ. MATCH Commun. Math. Comput. Chem. 2007;57:235.
10. Pan X, Yang C, Zhou MJ. MATCH Commun. Math. Comput. Chem. 2007;57:371.
11. Wagner SG. MATCH Commun. Math. Comput. Chem. 2007;57:221.
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.