Skip to content
/ eulerian Public

Count eulerian graphs on an n-dimensional hypercube

Notifications You must be signed in to change notification settings

hvds/eulerian

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

13 Commits
 
 
 
 
 
 
 
 

Repository files navigation

Calculate the number of Eulerian graphs on an n-dimensional hypercube.

A Eulerian graph is one in which each edge has a direction, and for
each vertex the number of edges directed "out of" this vertex is
equal to the number of edges directed "in to" it.

So by definition each vertex must have an even number of edges,
and thus "n" is required to be even.

It is known that for n=2 there are 2 such graphs, and for n=4 there
are 2970. It is additionally known that for n=6 the number lies
between 2.9 x 10^25 and 4.3 x 10^41 [1].

The aim is to calculate the value for n=6; for now, we assume n=8 is
out of reach.

[1] "Bounds on the Number of Eulerian Orientations" (A. Schrijver, 1983)
shows that the number of Eulerian orientations of a 2k-regular graph on
n vertices is between (2^{-k} (2k choose k))^n and sqrt((2k choose k)^n).

About

Count eulerian graphs on an n-dimensional hypercube

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published