Orientations making k-cycles cyclic

DOI10.1007/S00373-016-1715-XMaRDI QIDQ503634zbMATH OpenOpenAlexFDO

Authors Zita Helle, Gábor Simonyi

Publication date 13 January 2017

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.06888

zbMATH Keywords

graph orientationorientation in roundsoriented cycle

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Extremal combinatorics (05D99)

Abstract: 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 $lceillo{g}_2(n-1)ceil$. More generally, we also determine the minimum number of orientations of $K_n$ 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'os concerning triangles and $3$-edge-colorings. Some variants of the problem are also considered.

Recommendations

• \(k\)-cyclic orientations of graphs
• scientific article; zbMATH DE number 1047732
• On the maximum number of cyclic triples in oriented graphs
• Cycles in oriented 3-graphs
• Color the cycles

Cites work

• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 881164 (Why is no real title available?)
• Explicit construction of exponential sized families of k-independent sets
• Families of \(k\)-independent sets
• Fredman–Komlós bounds and information theory
• On the Size of Separating Systems and Families of Perfect Hash Functions

Cited in

(8)

• Bounds on the number of compatible \(k\)-simplices matching the orientation of the \((k-1)\)-skeleton of a simplex
• A note on the minimum number of edges in hypergraphs with property O
• Series-parallel orientations preserving the cycle-radius
• Quasirandom-Forcing Orientations of Cycles
• On colorful edge triples in edge-colored complete graphs
• scientific article; zbMATH DE number 4091547 (Why is no real title available?)
• On the maximum number of cyclic triples in oriented graphs
• \(k\)-cyclic orientations of graphs

This page was built for publication: Orientations making \(k\)-cycles cyclic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q503634)