Odd cycles and -cycles in hypergraphs

DOI10.1016/J.DISC.2005.12.037MaRDI QIDQ2433709zbMATH OpenOpenAlexFDO

Authors André E. Kézdy, András Gyárfás, Michael Jacobson, Jeno Lehel

Publication date 30 October 2006

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2005.12.037

zbMATH Keywords

bipartite graphextremal problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Hypergraphs (05C65)

Review text

A \(\Theta\)-cycle in a hypergraph \(H = (V,E)\) is a cycle plus an edge that contains three base points of the cycle. It is shown that if a hypergraph has no \(\Theta\)-cycle and all edges have at least three vertices, then \(\sum_{e \in E} (| e| - 1) \leq 2 | V| - 2\). In consequence, \(3\)-uniform hypergraphs having \(n\) vertices and \(n\) edges do have \(\Theta\)-cycles. For \(3\)-uniform linear hypergraphs, superiour bounds on the number of edges forcing a \(\Theta\)--cycle or an odd cycle are given.

Recommendations

• Hypergraphs with no odd cycle of given length
• 3-uniform hypergraphs avoiding a given odd cycle
• On 3-uniform hypergraphs without linear cycles
• On 3-uniform hypergraphs without a cycle of a given length
• Hypergraphs with no cycle of a given length

Cites work

• A class of hypergraphs satisfying an inequality of Lovasz
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• scientific article; zbMATH DE number 3407723 (Why is no real title available?)
• Minimally 2-connected graphs.
• On a Class of Totally Unimodular Matrices
• On Minimal Blocks

Cited in

(5)

• Stability and venture structures in multilateral matching
• On the theta number of powers of cycle graphs
• Hypergraphs with no cycle of a given length
• The extremal function for cycles of length \(\ell\) mod \(k\)
• Higher-order group synchronization

This page was built for publication: Odd cycles and \(\Theta\)-cycles in hypergraphs

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