In-tournament digraphs (Q1322037): Difference between revisions

We introduce a generalization of digraphs that are local tournaments. This is the class of in-tournament digraphs---the set of predecessors of every vertex induces a tournament. We show that many properties of local tournament digraphs can be extended even to in-tournament digraphs. For instance, any strongly connected in-tournament digraph has a directed Hamiltonian cycle. We prove that the underlying graph of any in- tournament digraph is 1-homotopic. We investigate the problem of which graphs are orientable as in-tournament digraphs and prove that any graph representable as an intersection subgraph of a unicyclic graph can be so oriented. It is shown that there is a polynomial algorithm for recognizing those graphs that can be oriented as in-tournament digraphs.