Conditions for a bigraph to be super-cyclic

Abstract

A hypergraph $\mathcal{H}$ is super-pancyclic if for each $A\subseteq V(\mathcal{H})$ with $|A|\ge 3$, $\mathcal{H}$ contains a Berge cycle with base vertex set $A$. We present two natural necessary conditions for a hypergraph to be super-pancyclic, and show that in several classes of hypergraphs these necessary conditions are also sufficient for this. In particular, they are sufficient for every hypergraph $\mathcal{H}$ with $\delta (\mathcal{H})\ge \max \{|V(\mathcal{H})|,\frac{|E(\mathcal{H})|+10}{4}\}$. We also consider super-cyclic bipartite graphs: those are $(X,Y)$-bigraphs $G$ such that for each $A\subseteq X$ with $|A|\ge 3$, $G$ has a cycle $C_A$ such that $V(C_A)\cap X=A$. Such graphs are incidence graphs of super-pancyclic hypergraphs, and our proofs use the language of such graphs.

17 pages