Extending Properties of Tournaments to k-Traceable Oriented Graphs (11frg171)

Objectives

The primary objective is to maintain the momentum achieved at previous workshops in solving $k$-traceability problems. Specifically, we will investigate the following topics.

The TC for oriented graphs with independence number 2

We have recently shown that the the cases $k=7,8,9$ of the TC holds for oriented graphs with independence number 2. We would like to further extend this result or to at least reduce the bound on $n$ in Theorem 1(6).

As observed in cite{fk}, every nontraceable oriented graph contains a hypotraceable oriented graph of order at least $k+1$ as induced subdigraph. It remains an open question whether there exists a hypotraceable oriented graph of order greater than 8 having independence number 2. If none exists, then for $kgeq 8$, every $k$-traceable oriented graph with independence number 2 will be traceable.

Planar $k$-traceable oriented graphs

We know that for $kgeq 2$, every $k$-traceable digraph of order $n$ has minimum degree at least $n-k+1$. Hence, for $kgeq 2$, the order of a planar $k$-traceable digraph is at most $k+4$. We have constructed planar $k$-traceable oriented graphs of order $k+2$ for infinitely many $kgeq 1$. Of course, there are no planar tournaments of order greater than 4. It will be interesting to know whether there exists a planar $k$-traceable oriented graph of order $k+3$ or $k+4$ for some $k>2$.

We will also investigate whether there exist any nontraceable planar $k$-traceable oriented graphs.

The TC obviously holds for planar oriented graphs, and hence the PPC holds for planar 1-deficient oriented graphs. Another goal is to make further progress towards proving the PPC for planar oriented graphs.

Cycle structure of $k$-traceable oriented graphs

Moon cite{moon:subtournaments} noticed that strong tournaments are emph{vertex-pancyclic}---i.e., in every strong tournament on $nge3$ vertices each vertex belongs to a cycle of length $l$ for every $3le lle n$. In cite{cycles} we showed that this nice fact extends to $k$-traceable oriented graphs for $k=3,4$. (A digraph of order $nge t$ is emph{vertex-t-pancyclic} if each vertex belongs to a cycle of length $l$ for every $tle lle n$.)

begin{theorem}cite{cycles} label{thm:pancyclic}
For $k=2,3,4$ every strong $k$-traceable oriented graph of order at least $k+1$ is vertex-$(k+1)$-pancyclic.
end{theorem}

This theorem is best possible in two ways: for any $kge2$, the directed $(k+1)$-cycle is $k$-traceable and obviously contains only a $(k+1)$-cycle; secondly, the conclusion of Theorem ref{thm:pancyclic} does not hold for larger values of $k$, since (by Theorem ref{thm1}(2)) for each $kge5$ there exist strong $k$-traceable non-Hamiltonian oriented graphs.

However, non-Hamiltonicity is a rather modest failure of pancyclicity, and our investigations have left the following question open: does every strong $k$-traceable oriented graph $D$ of order $nge k+2$ contain cycles of all lengths from $k+1$ through $c(D)$ (where $c(D)$ denotes the emph{circumference} of $D$, i.e., the length of a longest cycle in $D$)? Thus it is possible---indeed plausible---that $k$-traceable oriented graphs possess quite a rich cycle structure, if less so for larger $k$. This is a natural and popular topic that we would like to research further.

Locally $k$-traceable oriented graphs as generalizations of local tournaments

A emph{local tournament} is an oriented graph in which the out-neighbours (in-neighbours, respectively) of any given vertex induce a tournament. Much work has been done on local tournaments (at least 20 papers on the subject are found immediately via MathSciNet), especially from the perspective of path and cycle structure. (For a recent contribution, see cite{meierlingandvolkmann:cycle}.) Regarding these oriented graphs equivalently as emph{locally 2-traceable oriented graphs}, the avenue immediately opens to asking similar structural questions for the emph{locally $k$-traceable oriented graphs} ($kge2$)---these being the oriented graphs in which the out-neighbours (in-neighbours, respectively) of any given vertex induce a $k$-traceable oriented graph. It is to be expected that larger values of $k$ result in less (or less easily provable) cycle and path structure, but even the cases $k=3$ and $k=4$ would be interesting.

Multipartite $k$-traceable oriented graphs

A emph{multipartite tournament} is an orientation of a complete multipartite graph. These oriented graphs---which again generalize the tournaments---have received even more attention than the local tournaments. In fact, a recent and extensive survey by Volkmann cite{volkmann:multipartite} on multipartite tournaments contains no fewer than 181 references. Again, the emphasis has been on path and cycle structure. Once again, we may view these graphs as emph{multipartite 2-traceable oriented graphs} and thus generalize the notion as follows: a emph{multipartite $k$-traceable oriented graph} shall mean an orientation $D$ of a multipartite graph such that any set of $k$ vertices, selected from $k$ distinct partite sets, induces a traceable subdigraph of $D$. It shall be interesting to see to what extent and in which form the cycle and path structure of multipartite tournaments extends to multipartite $k$-traceable oriented graphs, even just for $k=3$ or $k=4$.

S.A. van Aardt, J.E. Dunbar, M. Frick, P. Katreniv{c}, M.H. Nielsen, and O.R. Oellermann, Traceability of $k$-traceable oriented graphs, Disc. Math. 310(2010) 1325--1333.

S.A. van Aardt, J.E. Dunbar, M. Frick, M.H. Nielsen, and O.R. Oellermann, A traceability conjecture for oriented graphs, Electron. J. Combin. 15(1) (2008) R150.

S.A. van Aardt, J.E. Dunbar, M. Frick, M.H. Nielsen, and O.R. Oellermann, Characterizations of $k$-traceable graphs and oriented graphs, to appear in Utilitas Math.

S.A. van Aardt, J. E. Dunbar, M. Frick and M.H. Nielsen, Cycles in $k$-traceable oriented graphs, submitted.

S.A. van Aardt, M. Frick, P. Katreniv{c}, and M.H. Nielsen, The
order of hypotraceable oriented graphs, to appear in Disc. Math.

J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms
and Applications, Springer-Verlag, London, 2008.

J. Bang-Jensen, J. Huang, and E. Prisner, In-tournament digraphs, J. Combin. Theory Ser. B 59(2) (1993) 267--287.

J. Bang-Jensen, M.H. Nielsen, A. Yeo, Longest path partitions in generalizations of tournaments,
Disc. Math. 306 (2006) 1830--1839.

M. Frick and P. Katreniv{c}, Progress on the traceabilty
conjecture, Discrete Math. and Theor. Comp. Science 10(3) (2008) 105--114.

J.W. Moon, On subtournaments of a tournament, Canad. Math. Bull. 9(3) (1966) 297--301.

D. Meierling and L. Volkmann, Cycle factors in strongly connected local tournaments, Disc. Math. 310 (2010) 850--860.

L.E. Penn and D. Witte, When the Cartesian product of two directed cycles is hypohamiltonian, J. Graph Theory 7 (1983) 441--443.

L. Volkmann, Multipartite tournaments: A survey, Disc. Math. 307 (2007) 3097--3129.