Name
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. |
Year | Venue | DocType |
|---|---|---|
2017 | Discrete Applied Mathematics | Journal |
Volume | Citations | PageRank |
abs/1312.1172 | 0 | 0.34 |
References | Authors | |
15 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Johannes Köbler | 1 | 580 | 46.51 |
| Sebastian Kuhnert | 2 | 36 | 6.52 |
| Oleg Verbitsky | 3 | 191 | 27.50 |