graph.de.bruijn {igraph} | R Documentation

## De Bruijn graphs.

### Description

De Bruijn graphs are labeled graphs representing the overlap of strings.

### Usage

    graph.de.bruijn(m,n)

### Arguments

`m` | Integer scalar, the size of the alphabet. See details below.
`n` | Integer scalar, the length of the labels. See details below.

### Details

A de Bruijn graph represents relationships between strings. An alphabet of `m` letters are used and strings of length `n` are considered. A vertex corresponds to every possible string and there is a directed edge from vertex `v` to vertex `w` if the string of `v` can be transformed into the string of `w` by removing its first letter and appending a letter to it.

Please note that the graph will have `m` to the power `n` vertices and even more edges, so probably you don't want to supply too big numbers for `m` and `n`.

De Bruijn graphs have some interesting properties, please see another source, eg. Wikipedia for details.

### Value

A graph object.

### Author(s)

Gabor Csardi <csardi@rmki.kfki.hu>

### See Also

`graph.kautz`, `line.graph`

### Examples

    # de Bruijn graphs can be created recursively by line graphs as well
    g <- graph.de.bruijn(2,1)
    graph.de.bruijn(2,2)
    line.graph(g)

[Package igraph version 0.5.2 Index]