|
|
||
|
IMADA - Department of Mathematics and Computer Science |
|
In Graph Theory, perhaps the most natural class of directed graphs to study is the class of tournaments— namely those digraphs which contain exactly one arc between every two vertices. Indeed, much is known about tournaments and, not surprisingly, they have nice properties. An equivalent way of thinking of tournaments is as the oriented graphs in which every pair of vertices induces a traceable subdigraph— i.e., a subdigraph containing a Hamiltonian path. This view then suggests a generalization of the class: call an oriented graph k-traceable if each k-set of vertices induces a traceable subdigraph (for some k ∈ N). Then any tournament is k-traceable (for every k) and it turns out that several of the nice properties of tournaments extend to larger values of k. We shall discuss some results and open questions, as well as a conjecture. Finally, a couple unexplored ideas for further directions of this work will be mentioned. Host: Jørgen Bang-Jensen SDU HOME | IMADA HOME | Previous Page Daniel Merkle |