Universal caterpillars

For a class $\text{C}$ of graphs, denote by u($\text{C}$) the least value of m so that for some graph U on m vertices, every G ? $\text{C}$ occurs as a subgraph of U. In this note we obtain rather sharp bounds on u($\text{C}$) when $\text{C}$ is the class of caterpillars on n vertices, i.e., tree with property that the vertices of degree exceeding one induce a path.     

The number of caterpillars

A caterpillar is a tree which metamorphoses into a path when its cocoon of endpoints is removed. The number of nonisomorphic caterpillars with n+4 points is $\text{2}{}^{\mathrm{n}}\text{+ 2}{}^{\mathrm{<mtext>[</mtext><mtext>n</mtext><mtext>2</mtext><mtext>]</mtext>}}$. This neat formula is proved in two ways: first, as a special case of an application of Pólya's enumeration theorem which counts graphs with integer-weighted points; secondly, by an appropriate labeling of the lines of the caterpillar.     

On determination of caterpillars with four terminal vertices by their Laplacian spectrum

We consider the class of caterpillars with four terminal vertices. Here we prove that every of such caterpillar whose internal path differs in length from both 1 to 3 is uniquely determined by its Laplacian spectrum. Next we take into consideration the remaining two possibilities for the internal path. In the first situation we prove that there is exactly one caterpillar which is not determined by its Laplacian spectrum, while we find an infinite family of such caterpillars in the second. Finally, some observations are given.     

On the maslov index

In this paper we give four definitions of Maslov index and show that they all satisfy the same system of axioms and hence are equivalent to each other. Moreover, relationships of several symplectic and differential geometric, analytic, and topological invariants (including triple Maslov indices, eta invariants, spectral flow and signatures of quadratic forms) to the Maslov index are developed and formulae relating them are given. The broad presentation is designed with a view to applications both in geometry and in analysis. © 1994 John Wiley & Sons, Inc.     

Spanning caterpillars of a hypercube

Spanning trees of the hypercube Q_n have been recently studied by several authors. In this paper, we construct spanning trees of Q_n which are caterpillars and establish quantitative bounds for a caterpillar to span Q_n. As a corollary, we disprove a conjecture of Harary and Lewinter on the length of the spine of a caterpillar spanning Qⁿ. © 1997 John Wiley & Sons, Inc.     

One-legged caterpillars span hypercubes

The aim of this paper is to prove that any balanced caterpillar having 2ⁿ vertices and maximum degree 3 spans the n-dimensional hypercube.     

Joining caterpillars and stability of the tree center

The path-tableP(T) of a tree T collects information regarding the paths in T: for each vertex v, the row of P(T) relative to v lists the number of paths containing v of the various lengths. We call this row the path-row of v in T.Two trees having the same path-table (up to reordering the rows) are called path-congruent (or path-isomorphic).Motivated by Kelly-Ulam's Reconstruction Conjecture and its variants, we have looked for new necessary and sufficient conditions for isomorphisms between two trees.Path-congruent trees need not be isomorphic, although they are similar in some respects. In [P. Dulio, V. Pannone, Trees with path-stable center, Ars Combinatoria, LXXX (2006) 153-175] we have introduced the concepts of trunkTr(T) of a tree T and ramification of a vertex v∈V(Tr(T)), and proved that, if the ramification of the central vertices attains its minimum or maximum value, then the path-row of a central vertex is “unique”, i.e. it is different from the path-row of any non-central vertex (in fact, this uniqueness property of a central path-row holds for all trees of diameter less than 8, regardless of the ramification values).In this paper we prove that, for all other values of the ramification, and for all diameters greater than 7, there are trees in which the above uniqueness fails.     

On the Hosoya index of graphs

Let G be a (molecular) graph. The Hosoya index Z(G) of G is defined as the number of subsets of the edge set E(G) in which no two edges are adjacent in G, i.e., Z(G) is the total number of matchings of G. In this paper, we determine all the connected graphs G with n + 1 ≤ Z(G) ≤ 5n ? 17 for n ≥ 19. As a byproduct, the graphs of n vertices with Hosoya index from the second smallest value to the twenty first smallest value are obtained for n ≥ 19.     

On the extremal Merrifield-Simmons index and Hosoya index of quasi-tree graphs

It is well known that the two graph invariants, “the Merrifield-Simmons index” and “the Hosoya index” are important in structural chemistry. A graph G is called a quasi-tree graph, if there exists u₀ in V(G) such that G−u₀ is a tree. In this paper, at first we characterize the n-vertex quasi-tree graphs with the largest, the second-largest, the smallest and the second-smallest Merrifield-Simmons indices. Then we characterize the n-vertex quasi-tree graphs with the largest, the second-largest, the smallest and the second-smallest Hosoya indices, as well as those n-vertex quasi-tree graphs with k pendent vertices having the smallest Hosoya index.     

On Thon's axiomatization of the Gini index

We give a short proof of Thon's characterization of the Gini index.