Orientations Making k-Cycles Cyclic

Helle, Zita and Simonyi, Gábor (2016) Orientations Making k-Cycles Cyclic. GRAPHS AND COMBINATORICS, 32 (6). pp. 2415-2423. ISSN 0911-0119

	Text art3A10.10072Fs00373_016_1715_x_u.pdf Restricted to Registered users only Download (423kB) | Request a copy
Preview	Text 1502.06888.pdf Download (661kB) | Preview

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 ⌈ log 2(n- 1) ⌉. 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. Though only formally related, 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. © 2016, Springer Japan.

Actions (login required)

Edit Item