×

zbMATH — the first resource for mathematics

Squaring the tournament—an open problem. (English) Zbl 0904.05034
Summary: Let \(T\) be a tournament. We define the digraph \(T^2\) on the vertices of \(T\) as follows: For all vertices \(x\) and \(y\) of \(T\), if \((x,y)\) is an arc in \(T\) then \((x,y)\) is an arc in \(T^2\) and if \((x,y)\) is an arc in \(T\) and there is a vertex \(z\) making \(\{x,y,z\}\) a 3-cycle in \(T\) then \((y,x)\) is an arc in \(T^2\).
Dean has conjectured that there is some vertex whose outdegree in \(T\) is at least doubled in \(T^2\). This is a special case of a conjecture of Seymour’s for oriented graphs. We prove Dean’s conjecture for several families of tournaments.

MSC:
05C20 Directed graphs (digraphs), tournaments
Keywords:
tournament; digraph
PDF BibTeX XML Cite