Displaying similar documents to “The algebraic connectivity of two trees connected by an edge of infinite weight.”

Statuses and branch-weights of weighted trees

Chiang Lin, Jen-Ling Shang (2009)

Czechoslovak Mathematical Journal

Similarity:

In this paper we show that in a tree with vertex weights the vertices with the second smallest status and those with the second smallest branch-weight are the same.

Constructions for type I trees with nonisomorphic Perron branches

Stephen J. Kirkland (1999)

Czechoslovak Mathematical Journal

Similarity:

A tree is classified as being type I provided that there are two or more Perron branches at its characteristic vertex. The question arises as to how one might construct such a tree in which the Perron branches at the characteristic vertex are not isomorphic. Motivated by an example of Grone and Merris, we produce a large class of such trees, and show how to construct others from them. We also investigate some of the properties of a subclass of these trees. Throughout, we exploit connections...

Constrained Steiner trees in Halin graphs

Guangting Chen, Rainer E. Burkard (2003)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

In this paper, we study the problem of computing a minimum cost Steiner tree subject to a weight constraint in a Halin graph where each edge has a nonnegative integer cost and a nonnegative integer weight. We prove the NP-hardness of this problem and present a fully polynomial time approximation scheme for this NP-hard problem.