×

3-uniform hypergraphs: modular decomposition and realization by tournaments. (English) Zbl 1447.05144

Summary: Let \(H\) be a 3-uniform hypergraph. A tournament \(T\) defined on \(V(T)=V(H)\) is a realization of \(H\) if the edges of \(H\) are exactly the 3-element subsets of \(V(T)\) that induce 3-cycles. We characterize the 3-uniform hypergraphs that admit realizations by using a suitable modular decomposition.

MSC:

05C65 Hypergraphs
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] P. Bonizzoni and G. Della Vedova,An algorithm for the modular decomposition of hypergraphs, J. Algorithms32(1999), 65-86. · Zbl 0942.68095
[2] A. Boussa¨ıri, P. Ille, G. Lopez, and S. Thomass´e,TheC3-structure of the tournaments, Discrete Math.277(2004), 29-43. · Zbl 1037.05024
[3] M. Chein, M. Habib, and M. C. Maurer,Partitive hypergraphs, Discrete Math.37 (1981), 35-50. · Zbl 0478.05071
[4] A. Ehrenfeucht, T. Harju, and G. Rozenberg,The Theory of 2-structures, a framework for decomposition and transformation of graphs, World Scientific, 1999. · Zbl 0981.05002
[5] A. Ehrenfeucht and G. Rozenberg,Theory of 2-structures, Part II: representations through tree labelled families, Theoret. Comput. Sci.70(1990), 305-342. · Zbl 0701.05052
[6] N. D. Filippov and L. N. Shevrin,Partially ordered sets and their comparability graphs, Siberian Math. J.11(1970), 497-509. · Zbl 0214.23303
[7] P. Frankl and Z. F¨uredi,An exact result for 3-graphs, Discrete Math.50(1984), 323-328. · Zbl 0538.05050
[8] T. Gallai,Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar.18(1967), 25-66. · Zbl 0153.26002
[9] A. Ghouila-Houri,Caract´erisation des graphes non orient´es dont on peut orienter les arˆetes de mani‘ere ‘a obtenir le graphe d’une relation d’ordre, C. R. Acad. Sci. Paris S´erie I254(1962), 1370-1371. · Zbl 0105.35503
[10] D. Haglin and M. Wolf,On convex subsets in tournaments, SIAM J. Discrete Math. 9(1996), 63-70. · Zbl 0858.05050
[11] P. Ille and J.-X. Rampon,A Counting of the minimal realizations of the posets of dimension two, Ars Combin.78(2006), 157-165. · Zbl 1164.06302
[12] P. Ille and R. Woodrow,Weakly partitive families on infinite sets, Contrib. Discrete Math.4(2009), 54-80. · Zbl 1203.05013
[13] D. Kelly,Comparability graphs, pp. 3-40, Reidel Publishing, 1985. · Zbl 0573.05055
[14] F. Maffray and M. Preissmann,A translation of Tibor Gallai’s paper: Transitiv orientierbare Graphen, pp. 25-66, Wiley, 2001. · Zbl 0989.05050
[15] J. H. Schmerl and W. T. Trotter,Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math.113(1993), 191-205. · Zbl 0776.06002
[16] J. Spinrad,
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.