Orientations making k-cycles cyclic

DOI10.1007/S00373-016-1715-XzbMATH Open1353.05070arXiv1502.06888OpenAlexW1577392775MaRDI QIDQ503634FDOQ503634

Authors: Zita Helle, Gábor Simonyi 

Publication date: 13 January 2017

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

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.

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

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

zbMATH Keywords

graph orientationorientation in roundsoriented cycle

Mathematics Subject Classification ID

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

Cites Work

• Families of \(k\)-independent sets
• On the Size of Separating Systems and Families of Perfect Hash Functions
• Fredman–Komlós bounds and information theory
• Title not available (Why is that?)
• Explicit construction of exponential sized families of k-independent sets
• Title not available (Why is that?)

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
• Title not available (Why is that?)
• 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)