Graph::Maker::Keller - create Keller graphs
use Graph::Maker::Keller; $graph = Graph::Maker->new ('Keller', N => 2);
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.
Graph::Maker::Keller
Graph.pm
The 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 2 or more digit positions, 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 (so a regular graph) 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 no digits and a single digit respectively, so nothing differs in 2 digit positions.
N=2 (16 vertices and 40 edges) is the Clebsch graph, which is the 16-cyclotomic graph.
The graph diameter is 2, for N>=2. A pair of vertices u,v not connected by an edge either don't have a digit differing 2 mod 4, or do but that is the sole difference. For the latter, a common intermediate is formed simply by a different digit at one of the other positions. For the former, take an intermediate differing from u by 2 mod 4 at one digit position, and differing from v by 2 mod 4 at another digit position.
subgraph => 1 gives the subgraph of the Keller graph induced by neighbours of vertex 0. This means the neighbours of vertex 0 (and not 0 itself) and the edges among those neighbours.
subgraph => 1
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 and 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.
$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().
graph_maker
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.
undirected => 1
House of Graphs entries for graphs here include
https://hog.grinvin.org/ViewGraphInfo.action?id=1310 (etc)
1310 N=0 (singleton) 52 N=1 (4 singletons) 975 N=2 (Clebsch, 16-cyclotomic) 34165 N=3
And subgraph option
subgraph
62 N=2 (5 singletons) 22730 N=3 22732 N=4
Entries in Sloane's Online Encyclopedia of Integer Sequences related to these graphs include
http://oeis.org/A202604 (etc)
A284838 num edges A202604 clique numbers (size of maximum clique) A258935 independence number A292056 Wiener index A301571 num vertices at distance 2 (3^N + N - 1)
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.
The second DIMACS challenge 1993 included the N=4 subgraph among its benchmarks for comparing clique-finding algorithms, http://dimacs.rutgers.edu/Challenges/
http://user42.tuxfamily.org/graph-maker-other/index.html
Copyright 2015, 2016, 2017, 2018, 2019, 2020, 2021 Kevin Ryde
This file is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
This file is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with This file. If not, see http://www.gnu.org/licenses/.
To install Graph::Maker::Other, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Graph::Maker::Other
CPAN shell
perl -MCPAN -e shell install Graph::Maker::Other
For more information on module installation, please visit the detailed CPAN module installation guide.