Circular-arc hypergraphs: Rigidity via Connectedness

Abstract

A circular-arc hypergraph $H$ is a hypergraph admitting an arc ordering, that is, a circular ordering of the vertex set $V(H)$ such that every hyperedge is an arc of consecutive vertices. An arc ordering is tight if, for any two hyperedges $A$ and $B$ such that $A$ is a nonempty subset of $B$ and $B$ is not equal to $V(H)$, the corresponding arcs share a common endpoint. We give sufficient conditions for $H$ to have, up to reversing, a unique arc ordering and a unique tight arc ordering. These conditions are stated in terms of connectedness properties of $H$. It is known that $G$ is a proper circular-arc graph exactly when its closed neighborhood hypergraph $N[G]$ admits a tight arc ordering. We explore connectedness properties of $N[G]$ and prove that, if $G$ is a connected, twin-free, proper circular-arc graph with non-bipartite complement, then $N[G]$ has, up to reversing, a unique arc ordering. If the complement of $G$ is bipartite and connected, then $N[G]$ has, up to reversing, two tight arc orderings. As a corollary, we notice that in both of the two cases $G$ has an essentially unique intersection representation. The last result also follows from the work by Deng, Hell, and Huang based on a theory of local tournaments.

21 pages, 8 figures

Cited by in corpus (2)

• Minimal and minimum unit circular-arc models
• Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space