In this paper we introduce the concept of directed hypergraph. It is a generalisation of the concept of digraph and is closely related with hypergraphs. The basic idea is to take a hypergraph, partition its edges non-trivially (when possible), and give a total order to such partitions. The elements of these partitions are called levels. In order to preserve the structure of the underlying hypergraph, we ask that only vertices which belong to exactly the same edges may be in the same level of any edge they belong to. Some little adjustments are needed to avoid directed walks within a single edge of the underlying hypergraph, and to deal with isolated vertices. The concepts of independent set, absorbent set, and transversal set are inherited directly from digraphs. As a consequence of our results on this topic, we have found both a class of kernel-perfect digraphs with odd cycles and a class of hypergraphs which have a strongly independent transversal set.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1449,
author = {Hortensia Galeana-S\'anchez and Mart\'\i n Manrique},
title = {Directed hypergraphs: a tool for researching digraphs and hypergraphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {29},
year = {2009},
pages = {313-335},
zbl = {1194.05051},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1449}
}
Hortensia Galeana-Sánchez; Martín Manrique. Directed hypergraphs: a tool for researching digraphs and hypergraphs. Discussiones Mathematicae Graph Theory, Tome 29 (2009) pp. 313-335. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1449/
[000] [1] J. Bang-Jensen and G. Gutin, Digraphs. Theory, Algorithms and Applications (Springer-Verlag London, London, UK, 2001). | Zbl 0958.05002
[001] [2] C. Berge, The Theory of Graphs (Dover Publications, New York, USA, 2001). | Zbl 0993.05001
[002] [3] C. Berge, Hypergraphs. Combinatorics of Finite Sets (Elsevier Science Publishers, Amsterdam, Holland, 1989).
[003] [4] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (MacMillan Press, London, UK, 1976). | Zbl 1226.05083
[004] [5] M. Borowiecki, Connected Bijection Method in Hypergraph Theory and Some Results Concerning the Structure of Graphs and Hypergraphs (Wydawnictwo Uczelniane, Zielona Góra, Poland, 1979). | Zbl 0425.05040
[005] [6] G. Chartrand and L. Lesniak, Graphs and Digraphs (Wadsworth Inc, Belmont, USA, 1986). | Zbl 0666.05001
[006] [7] P. Duchet, Graphes noyau-parfaites, Ann. Discrete Math. 9 (1980) 93-101, doi: 10.1016/S0167-5060(08)70041-4. | Zbl 0462.05033
[007] [8] P. Duchet and H. Meyniel, A Note on Kernel-critical Graphs, Discrete Math. 33 (1981) 103-105, doi: 10.1016/0012-365X(81)90264-8. | Zbl 0456.05032
[008] [9] H. Galeana-Sánchez and V. Neumann-Lara, On Kernels and Semikernels of Digraphs, Discrete Math. 48 (1984) 67-76, doi: 10.1016/0012-365X(84)90131-6. | Zbl 0529.05024
[009] [10] H. Galeana-Sánchez and V. Neumann-Lara, On Kernel-imperfect Critical Digraphs, Discrete Math. 59 (1986) 257-265, doi: 10.1016/0012-365X(86)90172-X. | Zbl 0593.05034
[010] [11] T. Haynes, S. Hedetniemi and P. Slater, Domination in Graphs (Marcel Dekker Inc. New York, USA, 1998). | Zbl 0890.05002
[011] [12] V. Neumann-Lara, Seminúcleos de una digráfica, An. Inst. Mat. UNAM, México, II (1984) 67-76.
[012] [13] M. Richardson, Solutions of Irreflexive Relations, Ann. Math. USA 58 (1953) p. 573, doi: 10.2307/1969755.
[013] [14] M. Richardson, Extension Theorems for Solutions of Irreflexive Relations, Proc. Math. Acad. Sci. USA 39 (1953) p. 649, doi: 10.1073/pnas.39.7.649. | Zbl 0053.02903