๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The bandwidth of a tree with k leaves is at most [k2]

โœ Scribed by Kiyoshi Ando; Atsusi Kaneko; Severino Gervacio

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
171 KB
Volume
150
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

The bandwidth B(G) of a finite simple graph G is the minimum of the quantity max{ If(x)-f(Y)I:xyC E(G)} taken over all injective integer labellings f of G. We prove that if a tree T has k leaves then B(T)<~ [k/2~. This improves the previously known upper bound

B(T)<.IV(T)I/2

๐Ÿ“œ SIMILAR VOLUMES

The maximal size of graphs with at most
The maximal size of graphs with at most k edge-disjoint paths connecting any two adjacent vertices
โœ Mao-cheng Cai ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 502 KB

Let n and k be positive integers satisfying k + 1 s n s 3k -1, and G a simple graph of order n and size e(G) with at most k edge-disjoint paths connecting any two adjacent vertices. In this paper we prove that e(G) s l(n + k)\*/8], and give complete characterizations of the extremal graphs and the e

A lower bound on the number of spanning
A lower bound on the number of spanning trees with k end-vertices
โœ Katherine Heinrich; Guizhen Liu ๐Ÿ“‚ Article ๐Ÿ“… 1988 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 286 KB ๐Ÿ‘ 1 views

If a graph G with cycle rank p contains both spanning trees with rn and with n end-vertices, rn < n, then G has at least 2p spanning trees with k end-vertices for each integer k, rn < k < n. Moreover, the lower bound of 2p is best possible. [ l ] and Schuster [4] independently proved that such span

On the reaction of the NH2 radical with
On the reaction of the NH2 radical with NO at 295โ€“620 K
โœ V.P. Bulatov; A.A. Ioffe; V.A. Lozovsky; O.M. Sarkisov ๐Ÿ“‚ Article ๐Ÿ“… 1989 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 460 KB

The reaction of the NH, radical with NO, NH2 +NO+k, products, was investigated using intracavity laser spectroscopy. The temperature dependence of k, [T) over the range 295-620 K is well approximated by the expression k, ( T) = (2,0? 0.4) X 1 O-'I x (T/298)-"' cm3 s-l. The branching ratios for the