Cycles in oriented 3-graphs

DOI10.1007/S00454-015-9702-1zbMATH Open1326.05054arXiv1409.0972OpenAlexW1647349209MaRDI QIDQ894680FDOQ894680

Ta Sheng Tan, Imre Leader

Publication date: 2 December 2015

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• DIRECTED SIMPLICES IN HIGHER ORDER TOURNAMENTS
• On high-dimensional acyclic tournaments

Cited In (7)

• Cycles in \(k\)-traceable oriented graphs
• Cyclic triangle factors in regular tournaments
• On cycles in 3-connected graphs
• \(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)