Home | About | Journals | Submit | Contact Us | Français |

**|**HHS Author Manuscripts**|**PMC2871707

Formats

Article sections

Authors

Related links

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

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

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.

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}*) =

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)+{\displaystyle \sum _{v\in 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

$$\frac{Z(G)}{Z(G-u)}=1+{\displaystyle \sum _{v\in N(u)}\frac{Z((G-u)-v)}{Z(G-u)}}.$$

We define the “vertex topological index”

$$\zeta (G,v)=\frac{Z(G)}{Z(G-u)}$$

and obtain at once a recurrence for ζ:

$$\zeta (G,u)=1+{\displaystyle \sum _{v\in N(u)}\frac{1}{\zeta (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*_{1}, *C*_{2},…,*C _{k}* then

$$Z(G)=Z({C}_{1})Z({C}_{2})\cdots Z({C}_{k}).$$

(3)

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

$$\begin{array}{cc}\zeta (G,u)\hfill & =\frac{Z(G)}{Z(G-u)}\hfill \\ \hfill & =\frac{Z({C}_{1})Z({C}_{2})\cdots Z({C}_{k})}{Z({C}_{1}-u)Z({C}_{2})\cdots Z({C}_{k})}\hfill \\ \hfill & =\frac{Z({C}_{1})}{Z({C}_{1}-u)}\hfill \\ \hfill & =\zeta ({C}_{1},u).\hfill \end{array}$$

(4)

We now restrict our attention to the case where *T* is a tree with root *r*. Letting *r*_{1}, *r*_{2}, …, *r _{k}* be the neighbors of

*Given a tree T with root r as well as T _{i} and r_{i} as defined above*,

$$\zeta (T,r)=1+{\displaystyle \sum _{i}\frac{1}{\zeta ({T}_{i},{r}_{i})}}.$$

(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 *P*_{5} rooted at the central vertex *v*_{3} would be

$$\tau ({P}_{5},{v}_{3})=1+\frac{1}{1+\frac{1}{1}}+\frac{1}{1+\frac{1}{1}}.$$

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

- The value 1 is a tree expression associated with the single-vertex tree, i.e., τ(
*r, r*) = 1. - If τ
, 1 ≤_{i}*i*≤*k*are tree expressions then so is $\tau =1+{\displaystyle {\sum}_{i=1}^{k}\frac{1}{{\tau}_{i}}}$. Given that we have associated each rooted tree (*T*) with τ_{i}, r_{i}, we associate the rooted tree (_{i}*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

*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*_{5}, *v*_{3}) we obtain the value 2 which does not convey the true value of *Z*(*P*_{5}) = 8 or *Z*(*P*_{5} − *v*_{3}) = 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.

*If (T, r) is a rooted tree with rooted trees* (*T _{i}, r_{i}*)

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}* =

$$\begin{array}{cc}\frac{a}{b}\hfill & =1+{\displaystyle \sum _{i=1}^{k}\frac{1}{\tau ({T}_{i},{r}_{i})}}\hfill \\ \hfill & =1+{\displaystyle \sum _{i=1}^{k}\frac{{b}_{i}}{{a}_{i}}}\hfill \\ \hfill & =\frac{{a}_{1}{a}_{2}{a}_{3}\cdots {a}_{k}+{b}_{1}{a}_{2}{a}_{3}\cdots {a}_{k}+{a}_{1}{b}_{2}{a}_{3}\cdots {a}_{k}+\cdots {a}_{1}{a}_{2}{a}_{3}\cdots {b}_{k}}{{a}_{1}{a}_{2}{a}_{3}\cdots {a}_{k}}\hfill \end{array}$$

We now observe that

$$\begin{array}{cc}b\hfill & ={a}_{1}{a}_{2}\cdots {a}_{k}\hfill \\ \hfill & =Z({T}_{1})Z({T}_{2})\cdots Z({T}_{k})\hfill \\ \hfill & =Z(T-r)\hfill \end{array}$$

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

$$\frac{a}{b}=\zeta (T,r)=\frac{Z(T)}{Z(T-r)}$$

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

We can see this in action in our example

$$\begin{array}{cc}\tau ({P}_{5},{v}_{3})\hfill & =1+\frac{1}{1+\frac{1}{1}}+\frac{1}{1+\frac{1}{1}}\hfill \\ \hfill & =1+\frac{1}{2}+\frac{1}{2}\hfill \\ \hfill & =\frac{4}{4}+\frac{2}{4}+\frac{2}{4}=\frac{8}{4}\hfill \end{array}$$

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 $\tau =1+{\displaystyle {\sum}_{i}\frac{1}{{\tau}_{i}}}$. The initial “1” in the expression $1+{\displaystyle {\sum}_{i}\frac{1}{{\tau}_{i}}}$ will be called the “leading 1”; each of the τ* _{i}* expressions will in turn have leading 1s. We construct the rooted tree (

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.

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*_{1}) is a rooted tree with vertices *v*_{0}, *v*_{1}, …, *v _{n}* and vertex

- If the vertex set of
*T*is {*v*_{0}}, then λ(*T*,*v*_{0}) =*x*_{0}. - If the root is adjacent to vertices
*v*_{i1},*v*_{i2}, …,*v*and that_{ik}*C*is the component of_{j}*T*−*v*_{0}that contains*v*, then λ(_{ij}*T*,*v*_{0}) =*x*_{0}+ ∑1/λ(_{j}*C*,_{j}*v*)._{ij}

In the case of a path *P* = *v*_{0}*v*_{1} … *v _{n}* rooted at

$$\lambda (P,{v}_{0})={x}_{0}+\frac{1}{{x}_{1}+\frac{1}{{x}_{2}+\frac{1}{\ddots \frac{\ddots}{{x}_{n-1}+\frac{1}{{x}_{n}}}}}}$$

Hosoya and Gutman [8] point out that

$$\lambda (P,{v}_{0})=\frac{\text{det}\phantom{\rule{thinmathspace}{0ex}}M({x}_{0},{x}_{1},{x}_{2},\dots ,{x}_{n})}{\text{det}\phantom{\rule{thinmathspace}{0ex}}M({x}_{1},{x}_{2},\dots ,{x}_{n})}$$

where

$$M({d}_{1},{d}_{2},{d}_{3},\dots ,{d}_{k})=\left(\begin{array}{ccccccc}\hfill {d}_{1}\hfill & \hfill 1\hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill \\ \hfill -1\hfill & \hfill {d}_{2}\hfill & \hfill 1\hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill \\ \hfill \hfill & \hfill -1\hfill & \hfill {d}_{3}\hfill & \hfill 1\hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill \\ \hfill \hfill & \hfill \hfill & \hfill -1\hfill & \hfill {d}_{4}\hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill \\ \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \ddots \hfill & \hfill \hfill & \hfill \hfill \\ \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill {d}_{k-1}\hfill & \hfill 1\hfill \\ \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill -1\hfill & \hfill {d}_{k}\hfill \end{array}\right)$$

denotes the *k* × *k* tridiagonal matrix whose diagonal entries are *d*_{1}, …, *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

$$B{(G)}_{\mathit{\text{ij}}}=\{\begin{array}{cc}{x}_{i},\hfill & i=j;\hfill \\ 1,\hfill & i<j,{v}_{i}\phantom{\rule{thinmathspace}{0ex}}\text{adjacent to}\phantom{\rule{thinmathspace}{0ex}}{v}_{j};\hfill \\ -1,\hfill & i>j,{v}_{i}\phantom{\rule{thinmathspace}{0ex}}\text{adjacent to}\phantom{\rule{thinmathspace}{0ex}}{v}_{j};\hfill \\ 0,\hfill & i\ne j,{v}_{i}\phantom{\rule{thinmathspace}{0ex}}\text{not adjacent to}\phantom{\rule{thinmathspace}{0ex}}{v}_{j}.\hfill \end{array}$$

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*_{0}) is the rooted tree that produces the tree expression τ in Fig. 1,

$$\tau (T,{v}_{0})=1+\frac{1}{1}+\frac{1}{1+\frac{1}{1}}+\frac{1}{1+\frac{1}{1}}+\frac{1}{1+\frac{1}{1}+\frac{1}{1+\frac{1}{1}}},$$

then

$$\lambda (T,{v}_{0})={x}_{0}+\frac{1}{{x}_{1}}+\frac{1}{{x}_{2}+\frac{1}{{x}_{3}}}+\frac{1}{{x}_{4}+\frac{1}{{x}_{5}}}+\frac{1}{{x}_{6}+\frac{1}{{x}_{7}}+\frac{1}{{x}_{8}+\frac{1}{{x}_{9}}}},$$

and (suppressing the zero elements),

$$B(T)=\left(\begin{array}{cccccccccc}{x}_{0}\hfill & 1\hfill & 1\hfill & \hfill & 1\hfill & \hfill & 1\hfill & \hfill & \hfill & \hfill \\ -1\hfill & {x}_{1}\hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \hfill \\ -1\hfill & \hfill & {x}_{2}\hfill & 1\hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \hfill \\ \hfill & \hfill & -1\hfill & {x}_{3}\hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \hfill \\ -1\hfill & \hfill & \hfill & \hfill & {x}_{4}\hfill & 1\hfill & \hfill & \hfill & \hfill & \hfill \\ \hfill & \hfill & \hfill & \hfill & -1\hfill & {x}_{5}\hfill & \hfill & \hfill & \hfill & \hfill \\ -1\hfill & \hfill & \hfill & \hfill & \hfill & \hfill & {x}_{6}\hfill & 1\hfill & 1\hfill & \hfill \\ \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & -1\hfill & {x}_{7}\hfill & \hfill & \hfill \\ \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & -1\hfill & \hfill & {x}_{8}\hfill & 1\hfill \\ \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & -1\hfill & {x}_{9}\hfill \end{array}\right)$$

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

$$\text{det}\phantom{\rule{thinmathspace}{0ex}}B(T)={\displaystyle \sum _{\sigma \in {S}_{n}}{(-1)}^{\text{sgn}(\sigma )}{\displaystyle \prod _{i=1}^{n}{(B(T))}_{i,\sigma (i)}}}$$

then an *x _{j}* value occurs in a term if and only if σ(

We also note that if *G* − *v* has components *C*_{1}, *C*_{2}, …, *C _{k}* then there is a permutation matrix

We are now ready to prove our result.

*If* (*T, r*) *is a labeled tree then*

$$\lambda (T,r)=\frac{\text{det}\phantom{\rule{thinmathspace}{0ex}}B(T)}{\text{det}\phantom{\rule{thinmathspace}{0ex}}B(T-r)}$$

*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.*

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*_{0} = *r*, *v*_{1}, …, *v*_{n − 1}. Suppose further that *v _{i}* is labeled

$$\text{det}\phantom{\rule{thinmathspace}{0ex}}B(T)={x}_{0}\text{det}\phantom{\rule{thinmathspace}{0ex}}B(T-r)+{\displaystyle \sum _{j}\text{det}\phantom{\rule{thinmathspace}{0ex}}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

$$\frac{\text{det}\phantom{\rule{thinmathspace}{0ex}}B(T)}{\text{det}\phantom{\rule{thinmathspace}{0ex}}B(T-r)}={x}_{0}+{\displaystyle \sum _{j}\frac{\text{det}\phantom{\rule{thinmathspace}{0ex}}B(T-r-{v}_{{i}_{j}})}{\text{det}\phantom{\rule{thinmathspace}{0ex}}B(T-r)}}.$$

Finally, if *C _{j}* is the component of

$$\begin{array}{cc}\frac{\text{det}\phantom{\rule{thinmathspace}{0ex}}B(T-r-{v}_{{i}_{j}})}{\text{det}\phantom{\rule{thinmathspace}{0ex}}B(T-r)}\hfill & =\frac{\text{det}\phantom{\rule{thinmathspace}{0ex}}B({C}_{j}-{v}_{{i}_{j}})}{\text{det}\phantom{\rule{thinmathspace}{0ex}}B({C}_{j})}\hfill \\ \hfill & =\frac{1}{\lambda ({C}_{j},{v}_{{i}_{j}})}\hfill \end{array}$$

by the inductive hypothesis. Therefore,

$$\frac{\text{det}\phantom{\rule{thinmathspace}{0ex}}B(T)}{\text{det}\phantom{\rule{thinmathspace}{0ex}}B(T-r)}={x}_{0}+{\displaystyle \sum _{j}\frac{1}{\lambda ({C}_{j},{v}_{ij})}=\lambda (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.

*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*

Again, we analyze the determinant by means of the usual formula involving permutations σ *S _{n}*:

$$P(G)={\displaystyle \sum _{\sigma \in {S}_{n}}{(-1)}^{\text{sgn}(\sigma )}{\displaystyle \prod _{i=1}^{n}{(B(G))}_{i,\sigma (i)}}}.$$

(6)

The only permutations that contribute to the desired coefficient are those that have each of *i*_{1}, *i*_{2}, …, *i _{k}* as their only fixed points. Let σ be such a permutation and suppose that σ has a cycle of length at least 3. Let

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 *i*_{1}, *i*_{2}, …, *i _{k}* and transpose all of the remaining entries in pairs. Each transposition (

We close by noting the following corollaries.

*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).

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

$$\zeta (G,v)=\frac{P(G)(1,1,\dots ,1)}{P(G-v)(1,1,\dots ,1)}.$$

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

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.

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.

PubMed Central Canada is a service of the Canadian Institutes of Health Research (CIHR) working in partnership with the National Research Council's national science library in cooperation with the National Center for Biotechnology Information at the U.S. National Library of Medicine(NCBI/NLM). It includes content provided to the PubMed Central International archive by participating publishers. |