Cycles in oriented 3-graphs

DOI10.1007/S00454-015-9702-1MaRDI QIDQ894680zbMATH OpenOpenAlexFDO

Authors Imre Leader, Ta Sheng Tan

Publication date 2 December 2015

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

projective planescyclestournamentsoriented graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Finite affine and projective planes (geometric aspects) (51E15)

Abstract: An oriented 3-graph consists of a family of triples (3-sets), each of which is given one of its two possible cyclic orientations. A cycle in an oriented 3-graph is a positive sum of some of the triples that gives weight zero to each 2-set. Our aim in this paper is to consider the following question: how large can the girth of an oriented 3-graph (on $n$ vertices) be? We show that there exist oriented 3-graphs whose shortest cycle has length $frac{n}^{2}2(1+o(1))$: this is asymptotically best possible. We also show that there exist 3-tournaments whose shortest cycle has length $frac{n}^{2}3(1+o(1))$, in complete contrast to the case of 2-tournaments.

Recommendations

• Cycles of given length in oriented graphs
• On short cycles in triangle-free oriented graphs.
• Short cycles in oriented graphs
• On the maximum number of cyclic triples in oriented graphs
• scientific article; zbMATH DE number 1047732

Cites work

• scientific article; zbMATH DE number 3812514 (Why is no real title available?)
• scientific article; zbMATH DE number 3450230 (Why is no real title available?)
• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• scientific article; zbMATH DE number 3303831 (Why is no real title available?)
• Directed simplices in higher order tournaments
• On high-dimensional acyclic tournaments

Cited in

(8)

• Cycles in \(k\)-traceable oriented graphs
• Cyclic triangle factors in regular tournaments
• On cycles in 3-connected graphs
• Orientations making \(k\)-cycles cyclic
• \(D_ \lambda\)-cycles in 3-cyclable graphs
• A condition for a family of triangles to be orientable to a cyclic order
• Cyclability of 3-connected graphs
• On the maximum number of cyclic triples in oriented graphs

This page was built for publication: Cycles in oriented 3-graphs

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