2015/02/24 by Zita Helle, Helle, Zita, Gábor Simonyi +1
Computer Science · Engineering · Mathematics · #05C20 #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO #msc:05C20 #msc:05C35
paper · pdf · doi:10.48550/arxiv.1502.06888
9 pages
arxiv created 2015/02/24 · openalex publication_date 2015/02/24 · arxiv updated 2015/02/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that the minimum number of orientations of the edges of the n-vertex complete graph having the property that every triangle is made cyclic in at least one of them is \lceillog2(n-1)\rceil. More generally, we also determine the minimum number of orientations of Kn such that at least one of them orients some specific k-cycles cyclically on every k-element subset of the vertex set. The questions answered by these results were motivated by an analogous problem of Vera T. Sós concerning triangles and 3-edge-colorings. Some variants of the problem are also considered.