No Access

EULERIAN AND HAMILTONIAN DICYCLES IN DIRECTED HYPERGRAPHS

JULIO ARAUJO

COATI Project, INRIA and I3S (CNRS/UNS), 2004, Route des Lucioles, B.P. 93, F-06902 Sophia Antipolis Cedex, France

Search for more papers by this author

JEAN-CLAUDE BERMOND

COATI Project, INRIA and I3S (CNRS/UNS), 2004, Route des Lucioles, B.P. 93, F-06902 Sophia Antipolis Cedex, France

Search for more papers by this author

, and

GUILLAUME DUCOFFE

University of Nice-Sophia Antipolis, France

Search for more papers by this author

https://doi.org/10.1142/S1793830914500128Cited by:2 (Source: Crossref)

Abstract

In this paper, we generalize the concepts of Eulerian and Hamiltonian digraphs to directed hypergraphs. A dihypergraphH is a pair (𝒱(H), ℰ(H)), where 𝒱(H) is a non-empty set of elements, called vertices, and ℰ(H) is a collection of ordered pairs of subsets of 𝒱(H), called hyperarcs. It is Eulerian (resp. Hamiltonian) if there is a dicycle containing each hyperarc (resp. each vertex) exactly once. We first present some properties of Eulerian and Hamiltonian dihypergraphs. For example, we show that deciding whether a dihypergraph is Eulerian is an NP-complete problem. We also study when iterated line dihypergraphs are Eulerian and Hamiltonian. Finally, we study when the generalized de Bruijn dihypergraphs are Eulerian and Hamiltonian. In particular, we determine when they contain a complete Berge dicycle, i.e., an Eulerian and Hamiltonian dicycle.

Keywords:

AMSC: 05C65, 05C45

References

E. Arkinet al., Hamilton triangulations for fast rendering, Proc. 2nd Annual European Symp. Algorithms, ESA '94 (Springer-Verlag, London, UK, 1994) pp. 36–47. Google Scholar
J. Bang-Jensen and G. Gutin , Digraphs: Theory, Algorithms and Applications ( Springer Verlag , New York , 2010 ) . Google Scholar
J. Bang-Jensen and S. Thomassé, Decompositions and orientations of hypergraphs, Technical Report, 10, IMADA (2001) . Google Scholar
D. Barth and M.-C. Heydemann, A new digraphs composition, Research report, LRI, Université de Paris-Sud, Orsay, France (1995) . Google Scholar
D. Barth and M.-C. Heydemann, Discrete Appl. Math. 77(2), 99 (1996), DOI: 10.1016/S0166-218X(96)00130-8. Crossref, Google Scholar
J. Bartholdi III and P. Goldsman, IEEE Trans. Vis. Comput. Graph. 10, 484 (2004), DOI: 10.1109/TVCG.2004.14. Crossref, Google Scholar
J. Bartholdi III and P. Goldsman, Oper. Res. Lett. 32, 304 (2004), DOI: 10.1016/j.orl.2003.11.005. Crossref, Google Scholar
V. Batagelj and T. Pisanski, Publ. Inst. Math. Soc. 25(39), 16 (1979). Google Scholar
C. Berge , Graphs and Hypergraphs 6 ( North-Holland , Amsterdam , 1973 ) . Google Scholar
J.-C. Bermond, Ann. Discrete Math. 3, 21 (1978), DOI: 10.1016/S0167-5060(08)70494-1. Crossref, Google Scholar
J.-C. Bermond, R. W. Dawes and F. Ergincan, Networks 30(3), 205 (1997), DOI: 10.1002/(SICI)1097-0037(199710)30:3<205::AID-NET5>3.0.CO;2-P. Crossref, Google Scholar
J.-C. Bermond and F. Ergincan, Discrete Appl. Math. 68, 1 (1996), DOI: 10.1016/0166-218X(95)00046-T. Crossref, Google Scholar
J.-C. Bermond, F. Ergincan and M. Syska, Quisquater Festschrift, Lecture Notes in Computer Science 6805 (Springer-Verlag, Berlin, Heidelberg, 2011) pp. 25–34. Google Scholar
J.-C. Bermond and C. Peyrat, De Bruijn and Kautz networks: A competitor for the hypercube?, Proc. 1st Europe. Workshop Hypercubes Distributed Computers, eds. F. André and J.-P. Verjus (North-Holland, Rennes, 1989) pp. 279–293. Google Scholar
J. Bondy and U. Murty , Graph Theory with Applications , 2nd edn. 290 ( MacMillan , London , 2008 ) . Google Scholar
F. Caoet al., Discrete Math. 183(3), 27 (1998), DOI: 10.1016/S0012-365X(97)00079-4. Crossref, Google Scholar
G. Chang, F. Hwang and L.-D. Tong, Math. Comput. Model. 25(11), 83 (1997), DOI: 10.1016/S0895-7177(97)00086-1. Crossref, Google Scholar
G. Chang, F. Hwang and L.-D. Tong, J. Graph Theory 31, 1 (1999). Crossref, Google Scholar
D. Coudert, Algorithmique et optimisation de réseaux de communications optiques, Ph.D. thesis, Université de Nice Sophia-Antipolis (UNSA) (2001) . Google Scholar
D.-Z. Du and D. Hsu, Banach Center Pub. 25, 47 (1989). Crossref, Google Scholar
D.-Z. Duet al., J. Comb. Theory, Series B 52(1), 1 (1991), DOI: 10.1016/0095-8956(91)90084-W. Crossref, Google Scholar
D.-Z. Du, D. F. Hsu and F. K. Hwang, Math. Comput. Model. 17(11), 61 (1993), DOI: 10.1016/0895-7177(93)90253-U. Crossref, Google Scholar
D.-Z. Du, D. Hsu and D. J. Kleitman, Modification of consecutive-d digraphs, Interconnection Networks and Mapping and Scheduling Parallel Computations: Proc. DIMACS Workshop (American Mathematical Society, Providence, RI, 1994) pp. 75–85. Google Scholar
D.-Z. Du, H. Ngo and G. Peck, Discrete Math. 257, 371 (2002), DOI: 10.1016/S0012-365X(02)00436-3. Crossref, Google Scholar
D.-Z. Du, D. Hsu and G. Peck, Discrete Appl. Math. 38, 169 (1992), DOI: 10.1016/0166-218X(92)90131-S. Google Scholar
D.-Z. Du and F. K. Hwang, Networks 18(1), 27 (1988), DOI: 10.1002/net.3230180105. Crossref, Google Scholar
J. De Rumeur , Communications dans les Réseaux de Processeurs ( Masson , France , 1994 ) . Google Scholar
G. Ducoffe, Eulerian and Hamiltonian directed hypergraphs, Research Report 7893, INRIA (2012) . Google Scholar
A. Dudek, A. Frieze and A. Ruciński, Electron. J. Combin. 19, P46 (2012). Crossref, Google Scholar
D. Ferrero and C. Padró, Discrete Applied Mathematics 117, 15 (2002), DOI: 10.1016/S0166-218X(00)00333-4. Crossref, Google Scholar
D. Ferrero and C. Padró, Networks 39, 61 (2002), DOI: 10.1002/net.10013. Crossref, Google Scholar
J. Gómez, C. Padró and S. Pérennes, Discrete Appl. Math. 89(3), 107 (1998). Crossref, Google Scholar
F. K. Hwang, Oper. Res. Lett. 6(3), 125 (1987), DOI: 10.1016/0167-6377(87)90024-1. Crossref, Google Scholar
M. Imase and M. Itoh, IEEE Trans. Comput. C 30, 439 (1981). Google Scholar
P. Keevashet al., Discrete Math. 311, 544 (2011), DOI: 10.1016/j.disc.2010.11.013. Crossref, Google Scholar
D. Kühn, R. Mycroft and D. Osthus, J. Combin. Theory Ser. A 117, 910 (2010), DOI: 10.1016/j.jcta.2010.02.010. Crossref, Google Scholar
Z. Lonc and P. Naroski, Electron. J. Combin. 17(R144), 1 (2010). Google Scholar
S. Reddy, D. Pradhan and J. Kuhl, Directed graphs with minimal diameter and maximal connectivity, Technical Report, Oakland University, School of Engineering (1980) . Google Scholar
T. E. Stern and K. Bala , Multiwavelength Optical Networks: A Layered Approach ( Addison-Wesley Longman Publishing , Boston, MA, USA , 1999 ) . Google Scholar