Cycles of length 0 modulo k in directed graphs

DOI10.1016/0095-8956(89)90071-3MaRDI QIDQ1093650zbMATH OpenOpenAlexFDO

Authors Nathan Linial, Noga Alon

Publication date 1989

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0095-8956(89)90071-3

zbMATH Keywords

directed cycleregular digraphs

Mathematics Subject Classification ID

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

Review text

We show that every digraph D with minimum outdegree \(\delta\) and maximum indegree \(\Delta\) contains a directed cycle of length 0(mod k), provided \(e(\Delta \delta +1)(1-1/k)^{\delta}<1\). In particular, if \(\Delta <(2^{\delta}-e)/e\delta\) then D contains an even cycle.

Recommendations

• Even cycles in directed graphs
• Cycles and paths of many lengths in bipartite digraphs
• Short cycles in digraphs
• The Even Cycle Problem for Directed Graphs
• Disjoint directed cycles

Cites work

• Cycles in digraphs– a survey
• Even cycles in directed graphs
• Every 7-regular digraph contains an even cycle
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• On 3-chromatic hypergraphs
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• Sign-nonsingular matrices and even cycles in directed graphs

Cited in

(16)

• Even cycles in directed graphs
• On cycles of directed graphs
• Every 7-regular digraph contains an even cycle
• Note on alternating directed cycles
• Zero sum cycles in complete digraphs
• Majority colorings of sparse digraphs
• Cycle lengths in expanding graphs
• Cycle lengths modulo k in expanders
• Almost given length cycles in digraphs
• scientific article; zbMATH DE number 22956 (Why is no real title available?)
• An algorithmic approach to the Lovász local lemma. I
• A parallel algorithmic version of the local lemma
• The Even Cycle Problem for Directed Graphs
• LATIN 2004: Theoretical Informatics
• Divisible subdivisions
• Cyclic path homology of (di)graphs

This page was built for publication: Cycles of length 0 modulo k in directed graphs

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