✦ LIBER ✦

Trees Associated with the Motzkin Numbers

✍ Scribed by Alexander Kuznetsov; Igor Pak; Alexander Postnikov

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 179 KB
Volume: 76
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.1996.0094

No coin nor oath required. For personal study only.

✦ Synopsis

We consider plane rooted trees on n+1 vertices without branching points on odd levels. The number of such trees in equal to the Motzkin number M n . We give a bijective proof of this statement.

📜 SIMILAR VOLUMES

Trees with the minimum Wiener number

✍ Shu-Chung Liu; Li-Da Tong; Yeong-Nan Yeh 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 283 KB

The Wiener number (W) of a connected graph is the sum of distances for all pairs of vertices. As a graphical invariant, it has been found extensive application in chemistry. Considering the family of trees with n vertices and a fixed maximum vertex degree, we derive some methods that can strictly re

On the crossing numbers of Cartesian pro

On the crossing numbers of Cartesian products with trees

✍ Drago Bokal 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 204 KB

## Abstract Zip product was recently used in a note establishing the crossing number of the Cartesian product __K__~1~,__n__ □ __P__~m~. In this article, we further investigate the relations of this graph operation with the crossing numbers of graphs. First, we use a refining of the embedding metho

On the Ramsey number of trees versus gra

On the Ramsey number of trees versus graphs with large clique number

✍ Ronald J. Gould; Michael S. Jacobson 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 335 KB

Chvatal established that r(T,, K,,) = (m -1 ) ( n -1 ) + 1, where T, , , is an arbitrary tree of order m and K, is the complete graph of order n. This result was extended by Chartrand, Gould, and Polimeni who showed K, could be replaced by a graph with clique number n and order n + 5 provided n 2 3

On graphs with the maximum number of spa

On graphs with the maximum number of spanning trees

✍ Alexander K. Kelmans 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 814 KB

Let 3:; denote the set of simple graphs with n vertices and m edges, t ( G ) the number of spanning trees of a graph G , and F 2 H if t(K,\E(F))?t(K,\E(H)) for every s? max{u(F), u ( H ) } . We give a complete characterization of >-maximal (maximum) graphs in 3:; subject to m 5 n . This result conta

The tripartite Ramsey number for trees

✍ Julia Böttcher; Jan Hladký; Diana Piguet 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 338 KB

## Abstract We prove that for all ε>0 there are α>0 and __n__~0~∈ℕ such that for all __n__⩾__n__~0~ the following holds. For any two‐coloring of the edges of __K__~__n, n, n__~ one color contains copies of all trees __T__ of order __t__⩽(3 − ε)__n__/2 and with maximum degree Δ(__T__)⩽__n__^α^. This

Graphs with an extremal number of spanni

Graphs with an extremal number of spanning trees

✍ A. K. Kelmans 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB 👁 1 views