, if GB(d, n) is Hamiltonian then GK(d, n) is also Hamiltonian, but the converse is not true. That is why we use GK(d, n), hence Definition 18, for the proof. The case for which the Hamiltonian properties of GB(d, n) are not enough to conclude is this one
, Lemmas 12 and 13 are nearly enough for solving the case when n is odd. Indeed, they show that when n is odd, then there is a complete Berge dicycle in GBH 2 (d, n, d, n)
, n) has no complete Berge dicycle when n is odd and n is not a power of 3. This remaining proof will be given later, using another method
, If d ? 4, and n is coprime to d, then there is a complete Berge dicycle in GBH 2 (d, n, d, n)
, Hamiltonian decompositions of complete k-uniform hypergraphs, Discrete Mathematics, issue.22, pp.3103088-3095, 2010.
, Digraphs: theory, algorithms and applications, 2010.
DOI : 10.1007/978-1-84800-998-1
, A new digraphs composition with applications to de Bruijn and generalized de Bruijn digraphs, Discrete Applied Mathematics, vol.77, issue.2, pp.99-118, 1997.
DOI : 10.1016/S0166-218X(96)00130-8
, On partially directed eulerian multigraphs, pp.16-24
, Graphs and hypergraphs, 1976.
, Line Directed Hypergraphs, Lecture Notes in Computer Science, 2011.
DOI : 10.1007/978-3-642-28368-0_5
URL : https://hal.archives-ouvertes.fr/hal-00643785
, Graph theory with applications 2 n d edition, 2008.
, Super line-connectivity of consecutive-d digraphs, Discrete Mathematics, vol.183, issue.1-3, pp.27-38, 1998.
DOI : 10.1016/S0012-365X(97)00079-4
, The hamiltonian property of the consecutive-3 digraph, Mathematical and Computer Modelling, vol.25, issue.11, pp.2583-88, 1997.
DOI : 10.1016/S0895-7177(97)00086-1
, The consecutive-4 digraphs are Hamiltonian, Journal of Graph Theory, vol.10, issue.1, pp.1-6, 1999.
DOI : 10.1002/(SICI)1097-0118(199905)31:1<1::AID-JGT1>3.0.CO;2-I
, Algorithmique et optimisation dans les réseaux de télécommunications. HabilitationàHabilitation`Habilitationà diriger des recherches, 2010.
, Communications dans les réseaux de processeurs, 1994.
, The Hamiltonian property of consecutive-d digraphs, Mathematical and Computer Modelling, vol.17, issue.11, pp.61-63, 1993.
DOI : 10.1016/0895-7177(93)90253-U
, The Hamiltonian property of generalized de Bruijn digraphs, Journal of Combinatorial Theory, Series B, vol.52, issue.1, pp.1-8, 1991.
DOI : 10.1016/0095-8956(91)90084-W
, Connectivity of consecutive-d digraphs, Discrete Appl. Math, pp.37-38169, 1992.
, On hamiltonian consecutive-d digraphs, pp.47-55, 1989.
, On connectivity of consecutive-d digraphs, Discrete Mathematics, vol.257, issue.2-3, pp.371-384, 2002.
DOI : 10.1016/S0012-365X(02)00436-3
, Modification of consecutive-d digraphs, pp.75-85, 1995.
, Directed hypergraphs and applications, Discrete Applied Mathematics, vol.42, issue.2-3, pp.177-201, 1993.
DOI : 10.1016/0166-218X(93)90045-P
URL : http://doi.org/10.1016/0166-218x(93)90045-p
, Large generalized cycles, Discrete Applied Mathematics, vol.89, issue.1-3, pp.107-123, 1998.
, Handbook of Product Graphs 2 nd edition, 2011.
, The Hamiltonian property of linear functions, Operations Research Letters, vol.6, issue.3, pp.125-127, 1987.
DOI : 10.1016/0167-6377(87)90024-1
, Edge-connectivity of undirected and directed hypergraphs, 2003.
, On tours that contain all edges of a hypergraph. The electronic journal of combinatorics, 2010.
, Universal cycles for permutations, Discrete Mathematics, vol.309, issue.17, pp.5264-5270, 2009.
DOI : 10.1016/j.disc.2007.11.004
, Linear connectivity problems in directed hypergraphs, pq ? 1 = 2 is prime, pp.27-292592, 2009.
DOI : 10.1016/j.tcs.2009.02.038
, Let n = n ? . We denote by BGC ? (p, d, n) the digraph GB ? (d, n) ? C p
, If n is odd, then BGC(p, 2, n) is Hamiltonian if and only if for all prime number q such that q|n
, Suppose that there exists some i such that the vertex (i, k 0 ) precedes the vertex (2i, k 0 + 1) in C. Then the vertex ( j, k 0 ) must precede the vertex (2 j, k 0 + 1) in C, with j = i ? 2 ?1 . Furthermore, since 2 ?1 is a generator element in Z n , therefore each vertex (i, k 0 ) has to precede the vertex (2i, k 0 + 1) in C. Otherwise, each vertex (i, k 0 ) has to precede the vertex (2i + 1, k 0 + 1) in C, and so there are only two possibilities for a given k 0 . At the end, there are only 2 p possible Hamiltonian dicycles, namely : C 0 ,C 1 , . . . ,C 2 p ?1 , such that after a vertex (i, 0), the next vertex in C r whose label is also in Z n × {0} is (2 p i + r, 0) Then observe that C r is a Hamiltonian dicycle if and only if i ? 2 p i + r is a circular permutation. Clearly n is coprime to 2 p . By Theorem 30, a necessary condition for i ? 2 p i + r to be a circular permutation, because we can always choose r = 1, and in so doing gcd (n, 2 p ? 1, r) = 1
, If n is even, then BGC(p, 3, n) is Hamiltonian
, Vertex (2i, 0) is incident to vertex (6i + 1, 1) and vertex (2i + 1, 0) is incident to vertex (6i + 4, 1) Since n is even and 6i + 3 is odd, therefore 6i + 3 (mod n) is odd. Consequently, [(6i + 3, 1), (6i + 4, 1)] is a pair of interchange f ( j) for some j. Furthermore 6i + 3 = 6(i + 3 ?1 ) + 1, and so g(i) and g(i + 3 ?1 ) are linked together. Since 3 ?1 is a generator element in Z n , therefore all the pairs g(i) are connected. It is interesting to notice that no extra-pairs of interchange
, If n is odd, then BGC(p, 3, n) is Hamiltonian
, Domaine Universitaire -351, cours de la Libération -33405 Talence Cedex Centre de recherche INRIA Grenoble ? Rhône-Alpes : 655, avenue de l'Europe -38334 Montbonnot Saint-Ismier Centre de recherche INRIA Lille ? Nord Europe : Parc Scientifique de la Haute Borne -40, avenue Halley -59650 Villeneuve d'Ascq Centre de recherche INRIA Nancy ? Grand Est
, Domaine de Voluceau -Rocquencourt -BP 105 -78153 Le Chesnay Cedex Centre de recherche INRIA Rennes ? Bretagne Atlantique : IRISA, Campus universitaire de Beaulieu -35042 Rennes Cedex Centre de recherche INRIA Saclay ? Île-de-France, des Vignes : 4, rue Jacques Monod -91893 Orsay Cedex Éditeur INRIA -Domaine de Voluceau -Rocquencourt, BP 105 -78153 Le Chesnay Cedex (France) http://www.inria.fr ISSN, pp.249-6399