Loading [MathJax]/extensions/MathZoom.js
Displaying 101 –
120 of
593
Comparing q-ary relations on a set of
elementary objects is one of the most fundamental problems of
classification and combinatorial data analysis. In this paper the
specific comparison task that involves
classification tree structures (binary or not) is considered in this
context. Two mathematical representations
are proposed. One is defined in terms of a weighted binary relation;
the second uses a 4-ary relation.
The most classical approaches to tree comparison are discussed in the
context...
Two spanning trees T1 and T2 of a graph G are completely independent if, for any two vertices u and v, the paths from u to v in T1 and T2 are internally disjoint. For a graph G, we denote the maximum number of pairwise completely independent spanning trees by cist(G). In this paper, we consider cist(G) when G is a partial k-tree. First we show that [k/2] ≤ cist(G) ≤ k − 1 for any k-tree G. Then we show that for any p ∈ {[k/2], . . . , k − 1}, there exist infinitely many k-trees G such that cist(G)...
The eigenvalues of graphs are related to many of its combinatorial properties. In his fundamental work, Fiedler showed the close connections between the Laplacian eigenvalues and eigenvectors of a graph and its vertex-connectivity and edge-connectivity. We present some new results describing the connections between the spectrum of a regular graph and other combinatorial parameters such as its generalized connectivity, toughness, and the existence of spanning trees with bounded degree.
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.
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.
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 between...
We compute the Coxeter polynomial of a family of Salem trees, and also the limit of the spectral radii of their Coxeter transformations as the number of their vertices tends to infinity. We also prove that if z is a root of multiplicities for the Coxeter polynomials of the trees respectively, then z is a root for the Coxeter polynomial of their join, of multiplicity at least where .
The cutwidth is an important graph-invariant in circuit layout designs. The cutwidth of a graph G is the minimum value of the maximum number of overlap edges when G is embedded into a line. A caterpillar is a tree which yields a path when all its leaves are removed. An iterated caterpillar is a tree which yields a caterpillar when all its leaves are removed. In this paper we present an exact formula for the cutwidth of the iterated caterpillars.
We prove that the cutwidth of the r-dimensional mesh of d-ary trees is of order
, which improves and generalizes previous results.
Currently displaying 101 –
120 of
593