✦ LIBER ✦

Acyclic Hypergraph Projections

✍ Scribed by Aviv Lustig; Oded Shmueli

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 157 KB
Volume: 30
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1998.0965

No coin nor oath required. For personal study only.

✦ Synopsis

Hypergraphs can be partitioned into two classes: tree acyclic hypergraphs and cyclic hypergraphs. This paper analyzes a new class of cyclic hypergraphs called Xrings. Hypergraph H is an Xring if the hyperedges of H can be circularly ordered so that for every vertex, all hyperedges containing the vertex are consecutive; in addition, the vertices of no hyperedge may be a subset of the vertices of another hyperedge, and no vertex may appear in exactly one hyperedge. Let H 1 and H be two hypergraphs. A tree projection of H with respect to H is an 2 1 2 acyclic hypergraph H such that the vertices of each hyperedge in H appear 3 1 among the vertices of some hyperedge of H and the vertices of each hyperedge in 3 H appear among the vertices of some hyperedge of H . A polynomial time 3 2 algorithm is presented for deciding, given Xring H and arbitrary hypergraph H , 1 2 whether there exists a tree projection of H with respect to H . It is shown that 2 1 hypergraph H is an Xring iff a modified adjacency graph of H is a circular-arc graph. A linear time Xring recognition algorithm, for GYO reduced hypergraphs as inputs, is presented.

📜 SIMILAR VOLUMES

C-perfect hypergraphs

✍ Csilla Bujtás; Zsolt Tuza 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB

## Abstract Let \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{H}}=({{X}},{\mathcal{E}})$\end{document} be a hypergraph with vertex set __X__ and edge set \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{E}}$\end{document}. A C‐colori

Entropy Splitting Hypergraphs

✍ Gábor Simonyi 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 367 KB

Hypergraph entropy is an information theoretic functional on a hypergraph with a probability distribution on its vertex set. It is sub-additive with respect to the union of hypergraphs. In case of simple graphs, exact additivity for the entropy of a graph and its complement with respect to every pro

Enumeration of Hypergraphs

✍ Toru Ishihara 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 87 KB

In this paper, we will study enumeration of hypergraphs. Let S p be a symmetric group acting on a p-setX . It induces the permutation group S \* p acting on the set of all subsets of X . Our problem is reduced to finding a good formula for the cycle index of S \* p . A crucial point is to calculate

Hamiltonian chains in hypergraphs

✍ Katona, Gyula Y.; Kierstead, H. A. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 111 KB

A cyclic ordering of the vertices of a k-uniform hypergraph is called a hamiltonian chain if any k consecutive vertices in the ordering form an edge. For k = 2 this is the same as a hamiltonian cycle. We consider several natural questions about the new notion. The main result is a Dirac-type theorem

Covering Non-uniform Hypergraphs

✍ Endre Boros; Yair Caro; Zoltán Füredi; Raphael Yuster 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 160 KB

A subset of the vertices in a hypergraph is a cover if it intersects every edge. Let {(H) denote the cardinality of a minimum cover in the hypergraph H, and let us denote by g(n) the maximum of {(H) taken over all hypergraphs H with n vertices and with no two hyperedges of the same size. We show tha

Choosability in Random Hypergraphs

✍ Michael Krivelevich; Van H. Vu 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 155 KB

The choice number of a hypergraph H=(V, E) is the least integer s for which, for every family of color lists S=[S(v): v # V], satisfying |S(v)|=s for every v # V, there exists a choice function f so that f (v) # S(v) for every v # V, and no edge of H is monochromatic under f. In this paper we consid