The directed genus of the de Bruijn graph |
| |
| Authors: | Alfred W Hales Nora Hartsfield |
| |
| Institution: | aCenter for Communications Research, 4320 Westerra Court, San Diego, CA, 92121, USA;bDepartment of Mathematics, Western Washington University, Bellingham, WA 98225, USA |
| |
| Abstract: | Define the directed genus, Γ(G), of an Eulerian digraph G to be the minimum value of p for which G has a 2-cell embedding in the orientable surface of genus p so that every face of the embedding is bounded by a directed circuit in G. The directed genus of the de Bruijn graph Dn is shown to be |
| |
| Keywords: | Directed genus de Bruijn graph Directed embeddings de Bruijn sequence invariant |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
