Some remarks on the enumeration of the Douglas tournament
Davide C. Demaria, J. Carlos S. Kiihl
PRE-PRINT
Inglês
Agradecimentos: This work was performed under the auspices of the Consiglio Nazionale delle Ricerche (CNR, GNSAGA) and FAPESP (Proc. No 89/2042-1)
Abstract: In this paper we consider the enumeration problem of the Dn tournaments, which are the tournaments admitting exactly one hamiltonian cycle. Firstly we determine the number # D of the (non isomorphic) simple Dn tournaments. Then we determine the number # DN of the normal Dr tournaments,...
Ver mais
Abstract: In this paper we consider the enumeration problem of the Dn tournaments, which are the tournaments admitting exactly one hamiltonian cycle. Firstly we determine the number # D of the (non isomorphic) simple Dn tournaments. Then we determine the number # DN of the normal Dr tournaments, proving that # DN Fan-8, (n = 4), where F; is the j-th Fibonacci number. In such a way, without considering matrices we reobtain Garey's result that the number #Dn of all Dn tournaments is equal to F2n-6
Ver menos
FUNDAÇÃO DE AMPARO À PESQUISA DO ESTADO DE SÃO PAULO - FAPESP
89/2042-1
Aberto
Some remarks on the enumeration of the Douglas tournament
Davide C. Demaria, J. Carlos S. Kiihl
Some remarks on the enumeration of the Douglas tournament
Davide C. Demaria, J. Carlos S. Kiihl
Fontes
|
Relatório técnico n. 46, p. 1-18, nov. 1989 |