de Bruin Graph

Author

Eric W. Weisstein
March 7, 2017

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/deBruijnGraph.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/deBruijnGraph.html.

©2017 Wolfram Research, Inc. except for portions noted otherwise

Initialization

<<DiscreteMath`Combinatorica`

Usage

?DeBruijnGraph

Figure

Combinatorica

v4.1.5

<<DiscreteMath`Combinatorica`

?DeBruijnGraph

v4.2.1

DeBruijnGraph[2,2]//InputForm

v5.0

DeBruijnGraph[2,2]//InputForm

MakeBoxes[label[m_,n_],TraditionalForm]:=RowBox[{"(",RowBox[{MakeBoxes[m,TraditionalForm],",",MakeBoxes[n,TraditionalForm]}],")"}]

Show[GraphicsArray[
Block[{$DisplayFunction=Identity},
Table[
ShowGraph[
DeBruijnGraph[m,n],
PlotRange->All,
VertexStyle->Disk[.07],
VertexColor->Red,
PlotLabel->TraditionalForm[label[m,n]]
],{m,2,3},{n,1,4}]
]
],ImageSize->500]

Built-in

GraphicsGrid[Table[Show[DeBruijnGraph[m,n,VertexSize->{"Scaled",.05},System`EdgeStyle->Black,System`VertexStyle->Red],PlotLabel->{m,n}],{m,2,3},{n,1,4}],ImageSize->700]

Independence Number

A006946

1, 2, 3, 7, 13, 28, 55

DeBruijnGraph[2,{1,2}]

Length/@Table[FindIndependentVertexSet[DeBruijnGraph[2,n]][[1]],{n,3}]

Do[Print[{n,Length@FindIndependentVertexSet[DeBruijnGraph[2,n]][[1]]//Timing}],{n,7}]

FindIndependentVertexSet[DeBruijnGraph[2,7],{55}]//Timing

TimeConstrained[FindIndependentVertexSet[DeBruijnGraph[2,7],{56}],300]//Timing