✦ LIBER ✦

Onk-ary spanning trees of tournaments

✍ Scribed by Lu, Xiaoyun; Wang, Da-Wei; Chang, Gerard J.; Lin, In-Jen; Wong, C. K.

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 114 KB
Volume: 30
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199903)30:3<167::aid-jgt2>3.0.co;2-o

No coin nor oath required. For personal study only.

✦ Synopsis

It is well known that every tournament contains a Hamiltonian path, which can be restated as that every tournament contains a unary spanning tree. The purpose of this article is to study the general problem of whether a tournament contains a k-ary spanning tree. In particular, we prove that, for any fixed positive integer k, there exists a minimum number h(k) such that every tournament of order at least h(k) contains a k-ary spanning tree. The existence of a Hamiltonian path for any tournament is the same as h(1) = 1. We then show that h(2) = 4 and h(3) = 8. The values of h(k) remain unknown for k ≥ 4.

📜 SIMILAR VOLUMES

Spanning trees of dual graphs

✍ Norman Biggs 📂 Article 📅 1971 🏛 Elsevier Science 🌐 English ⚖ 210 KB

Shifts and loopless generation of k-ary

Shifts and loopless generation of k-ary trees

✍ James F. Korsh; Seymour Lipschutz 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 388 KB

A new shift operation on nodes of k-ary trees which preserves preorder node numbers is introduced. The shift graph SG,,k has as vertices all n-node k-ary trees and edges corresponding to one shift. The graph is proven to have a Hamiltonian path and an algorithm is presented which generates all n-nod

The number of tournaments with a unique

The number of tournaments with a unique spanning cycle

✍ J. W. Moon 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 312 KB 👁 1 views

## Abstract The number of tournaments __T~n~__ on __n__ nodes with a unique spanning cycle is the (2__n__‐6)th Fibonacci number when __n__ ≥ 4. Another proof of this result is given based on a recursive construction of these tournaments.

Minimum Spanning Trees and Types of Diss

Minimum Spanning Trees and Types of Dissimilarities

✍ Bruno Leclerc 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 295 KB

Natural spanning trees of Zd are recurre

Natural spanning trees of Zd are recurrent

✍ Peter Gerl 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 169 KB

We show that the simple random walk on the natural spanning tree of 7/d is recurrent for every d ( = 1, 2, 3,...) and determine the asymptotic behaviour of the probability of returning to the origin in n steps (n--, 0o). This is in contrast to a result of Polya [6]: Z d is recurrent for d = 1, 2 and

The number of spanning trees in buckmins

The number of spanning trees in buckminsterfullerene

✍ T. J. N. Brown; R. B. Mallion; P. Pollak; Branca R. M. de Castro; J. A. N. F. Go 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 662 KB

## Abstract The theorem of Gutman et al. (1983) is applied to calculate the number of spanning trees in the carbon‐carbon connectivity‐network of the recently diagnosed C~60~‐cluster buckminsterfullerene. This “complexity” turns out to be approximately 3.75 × 10^20^ and it is found necessary to inv