scientific article; zbMATH DE number 3884197
Let \(T_ n\) be a tournament with n vertices. A permutation \(x_ 1,x_ 2,...,x_ n\) of the vertices of \(T_ n\) gives rise to a sequence \((e_ 1,e_ 2,...,e_{n-2})\) of zeros and ones where (i) \(e_ i=0\) if \(x_ i\to x_{i+1}\) in \(T_ n\); \(e_ i=1\) if \(x_ i\leftarrow x_{i+1}\) in \(T_ n\). In the case where \(e_ i=1-e_{i-1}\) for \(i=2,3,...,n-1\), the path \(x_ 1,x_ 2,...,x_ n\) is called an antidirected Hamiltonian path. \textit{B. Grünbaum} [J. Comb. Theory, Ser. B 11, 249-257 (1971; Zbl 0198.293)] proved that, except for three special tournaments with 3, 5 and 7 vertices respectively, every tournament contains an antidirected Hamiltonian path. \textit{A. Thomason} [Paths and cycles in tournaments (to appear)] proved that if n is sufficiently large, for every tournament \(T_ n\) and every sequence \((e_ 1,e_ 2,...,e_{n-1})\) a path \(x_ 1,...,x_ n\) can be found satisfying (i). The author considers questions regarding the actual number of permutations of a given tournament which will satisfy a given sequence \(e_ 1,...,e_{n-1}\). The purpose of the paper, a continuation of previous work by the author, is to provide theorems and machinery regarding these numbers. He conjectures that these numbers belong to a matrix of rank n-2.
- Antidirected Hamiltonian paths between specified vertices of a tournament
- Oriented Hamiltonian paths in tournaments: A proof of Rosenfeld's conjecture
- Antidirected Hamiltonian paths and directed cycles in tournaments
- Hamiltonian paths containing a given arc, in almost regular bipartite tournaments
- The maximum number of Hamiltonian paths in tournaments
- Parity of paths in tournaments
- On the maximum number of Hamiltonian paths in tournaments
- Slater orders and Hamiltonian paths of tournaments
- The complexity of finding generalized paths in tournaments
- scientific article; zbMATH DE number 3855147 (Why is no real title available?)
- scientific article; zbMATH DE number 3902692 (Why is no real title available?)
- scientific article; zbMATH DE number 3914351 (Why is no real title available?)
- Hamilton Paths in Tournaments and a Problem of McMullen on Projective Transformations in R d
- scientific article; zbMATH DE number 4089591 (Why is no real title available?)
- scientific article; zbMATH DE number 589708 (Why is no real title available?)
- Hamiltonian Cycles in Regular Tournaments
- Realizing small tournaments through few permutations
- scientific article; zbMATH DE number 2221999 (Why is no real title available?)
- About the number of oriented Hamiltonian paths and cycles in tournaments
- Paths of given length in tournaments
- Construction of Hamilton path tournament designs
- A note on the number of Hamiltonian paths in strong tournaments
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3218154)