Counting orientations of random graphs with no directed k‐cycles

DOI10.1002/RSA.21196MaRDI QIDQ6201038zbMATH OpenFDO

Authors Marcelo Campos, Maurício Collares, G. O. Mota

Publication date 25 March 2024

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

directed cyclesorientationsrandom graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30) Paths and cycles (05C38) Random graphs (graph-theoretic aspects) (05C80)

Abstract: For every $kgeq3$, we determine the order of growth, up to polylogarithmic factors, of the number of orientations of the binomial random graph containing no directed cycle of length $k$. This solves a conjecture of Kohayakawa, Morris and the last two authors.

Recommendations

• On the number of orientations of random graphs with no directed cycles of a given length
• Counting restricted orientations of random graphs
• A note on counting orientations
• Spanning cycles in random directed graphs
• Packing and counting arbitrary Hamilton cycles in random digraphs

Cites work

• Counting H-free orientations of graphs
• Counting independent sets in graphs
• Counting orientations of graphs with no strongly connected tournaments
• Counting restricted orientations of random graphs
• scientific article; zbMATH DE number 3487496 (Why is no real title available?)
• On the number of graphs without 4-cycles
• On the number of orientations of random graphs with no directed cycles of a given length
• The number of oriantations having no fixed tournament
• The Theory of Round Robin Tournaments

This page was built for publication: Counting orientations of random graphs with no directed k‐cycles

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