++ed by:

1 non-PAUSE user.

Kevin Ryde
and 1 contributors

# NAME

Graph::Maker::Keller - create Keller graphs

# SYNOPSIS

`````` use Graph::Maker::Keller;
\$graph = Graph::Maker->new ('Keller', N => 2);``````

# DESCRIPTION

`Graph::Maker::Keller` creates a `Graph.pm` graph of a Keller graph. This is a graph form of Keller's conjecture on N-dimensional tilings by unit hypercubes.

Keller graph N has 4^N vertices numbered 0 to 4^N-1. These vertices are treated as base-4 integers. Edges are between vertices differing in two or more digit positions and at least one of which is difference 2 mod 4.

``````    N         0  1   2     3      4       5
vertices  1, 4, 16,   64,   256,   1024, ...  4^N
degree    0, 0,  5,   34,   171,    776, ...  4^N - 3^N - N
edges     0, 0, 40, 1088, 21888, 397312, ... (4^N-3^N-N)*4^N / 2``````

Each vertex has the same degree since digit differences can all be taken mod 4. Each vertex degree is 4^N - 3^N - N. This is edges to 4^N vertices (including self) except no edge to those differing by only 0,1,3 in any or all digit positions, which is 3^N combinations (including no differences at all for vertex itself), and also no edge to vertices differing by 2 mod 4 at a single digit, which is N possible digit positions.

N=0 and N=1 have no edges since there are only 0 digits and 1 digit respectively, so nothing differs in 2 digit positions.

N=2 (16 vertices and 40 edges) is the Clebsh graph and the 16-cyclotomic graph.

## Subgraph

`subgraph => 1` gives the subgraph of the Keller graph induced by neighbours of vertex 0. This means the neighbours of vertex 0 (not including 0 itself) and the edges among those neighbours.

``````    subgraph => 1
N         0  1   2     3      4       5
vertices  0, 0,  5,   34,   171,    776, ... 4^N - 3^N - N
edges     0, 0,  0,  261,  9435, 225990, ...``````

The number of vertices is the degree above. This subgraph is of interest since the Keller graph is vertex transitive so the problem of finding a clique of size k in the Keller graph is reduced to finding a clique of size k-1 in this subgraph. The size of the maximum clique is related to Keller's conjecture.

N=2 subgraph has no edges. Its vertices are 12, 21, 22, 23, 32 in base-4 and any pair of them either differ in only 1 digit or differ in 2 digits but without a difference 2 mod 4.

# FUNCTIONS

`\$graph = Graph::Maker->new('Keller', key => value, ...)`

The key/value parameters are

``````    N           => integer
subgraph    => 0 or 1, default 0
graph_maker => subr(key=>value) constructor, default Graph->new``````

Other parameters are passed to the constructor, either `graph_maker` or `Graph->new()`.

If the graph is directed (the default) then edges are added both forward and backward between vertices. Option `undirected => 1` creates an undirected graph and for it there is a single edge between vertices.

# HOUSE OF GRAPHS

House of Graphs entries for graphs here include

N=2, https://hog.grinvin.org/ViewGraphInfo.action?id=975 (Clebsch)
N=3 subgraph, https://hog.grinvin.org/ViewGraphInfo.action?id=22730
N=4 subgraph, https://hog.grinvin.org/ViewGraphInfo.action?id=22732

# OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to these graphs include

``    A202604    clique numbers (size of maximum clique)``

Graph::Maker

O. H. Keller, "Uber die luckenlose Einfullung des Raumes mit Wurfeln", Journal für die Reine und Angewandte Mathematik (Crelle's journal), volume 163, 1930, pages 231-248.