Generalized de Bruijn multigraphs of rank \(\overarrow k\)
type: Item
instance of: scholarly article
zbMATH Open document ID: 0963.05087
author: Zdzisław Grodzki
author: A. Wroński
publication date: 2001-06-10T00:00:00Z
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 1602774
zbMATH Keywords: de Bruijn graph
zbMATH Keywords: directed multigraph
zbMATH Keywords: Eulerian
zbMATH Keywords: Hamiltonian
MaRDI profile type: Publication
title: Generalized de Bruijn multigraphs of rank \(\overarrow k\)
published in: Ars Combinatoria
review text: Let \(A\) be a finite alphabet and \(V=A^{k_1}\times \cdots \times A^{k_m}\) for some positive integers \(k=(k_1,\ldots ,k_m)\). Let \(t\in V\) and \(a\in (A\cup \{*\})^m\), where \(*\not \in A\) and not all coordinates of \(a\) are \(*\). Elements \(t\) and \(a\) define uniquely a \(u\in V\): \(u_i=t_i\) if \(a_i=*\), else \(u_i\) arises from \(t_i\) by deleting the first term of \(t_i\in A^{k_i}\) and appending \(a_i\) to the end. A directed multigraph \(\text{GBG}_k=(V,E)\) is defined by putting in \(E\) all edges \((t,u)\) for all \(a\); \((t,u)\) is labelled by the corresponding \(a\). The \(\text{GBG}_k\) generalize the classical de Bruijn graphs (\(m=1\)). By a reduction to them it is shown that the \(\text{GBG}_k\) are connected, Eulerian, and Hamiltonian. An algorithm is presented for finding spanning subgraphs whose components are cycles.
reviewed by: Martin Klazar
description: scientific article; zbMATH DE number 1602774