Directed hypergraphs: a tool for researching digraphs and hypergraphs

Hortensia Galeana-Sánchez; Martín Manrique

Discussiones Mathematicae Graph Theory (2009)

  • Volume: 29, Issue: 2, page 313-335
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Hortensia Galeana-Sánchez, and Martín Manrique. "Directed hypergraphs: a tool for researching digraphs and hypergraphs." Discussiones Mathematicae Graph Theory 29.2 (2009): 313-335. <http://eudml.org/doc/270515>.

@article{HortensiaGaleana2009,
abstract = { 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. },
author = {Hortensia Galeana-Sánchez, Martín Manrique},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hypergraph; strongly independent set; transversal set; kernel},
language = {eng},
number = {2},
pages = {313-335},
title = {Directed hypergraphs: a tool for researching digraphs and hypergraphs},
url = {http://eudml.org/doc/270515},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Hortensia Galeana-Sánchez
AU - Martín Manrique
TI - Directed hypergraphs: a tool for researching digraphs and hypergraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 2
SP - 313
EP - 335
AB - 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.
LA - eng
KW - hypergraph; strongly independent set; transversal set; kernel
UR - http://eudml.org/doc/270515
ER -

References

top
  1. [1] J. Bang-Jensen and G. Gutin, Digraphs. Theory, Algorithms and Applications (Springer-Verlag London, London, UK, 2001). Zbl0958.05002
  2. [2] C. Berge, The Theory of Graphs (Dover Publications, New York, USA, 2001). Zbl0993.05001
  3. [3] C. Berge, Hypergraphs. Combinatorics of Finite Sets (Elsevier Science Publishers, Amsterdam, Holland, 1989). 
  4. [4] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (MacMillan Press, London, UK, 1976). Zbl1226.05083
  5. [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). Zbl0425.05040
  6. [6] G. Chartrand and L. Lesniak, Graphs and Digraphs (Wadsworth Inc, Belmont, USA, 1986). Zbl0666.05001
  7. [7] P. Duchet, Graphes noyau-parfaites, Ann. Discrete Math. 9 (1980) 93-101, doi: 10.1016/S0167-5060(08)70041-4. Zbl0462.05033
  8. [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. Zbl0456.05032
  9. [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. Zbl0529.05024
  10. [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. Zbl0593.05034
  11. [11] T. Haynes, S. Hedetniemi and P. Slater, Domination in Graphs (Marcel Dekker Inc. New York, USA, 1998). Zbl0890.05002
  12. [12] V. Neumann-Lara, Seminúcleos de una digráfica, An. Inst. Mat. UNAM, México, II (1984) 67-76. 
  13. [13] M. Richardson, Solutions of Irreflexive Relations, Ann. Math. USA 58 (1953) p. 573, doi: 10.2307/1969755. 
  14. [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. Zbl0053.02903

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.