TOPICS
Search

Keller Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The n-dimensional Keller graph, sometimes denoted G_n (e.g., Debroni et al. 2011), is the generalized Keller graph G_(n,2). Equivalently, its vertices are the n-tuples over the integers 0, 1, 2, and 3, with two vertices adjacent if they differ by 2 in at least one coordinate and differ in at least two coordinates. It has 4^n vertices.

KellerGraph

Special cases are summarized in the following table. The construction of the 2-Keller graph, which is isomorphic to the Clebsch graph, is illustrated above.

ngraph
14-empty graph K^__4
2Clebsch graph

The graphs G_n give a convenient graph-theoretic formulation of Keller's conjecture and have been used extensively for testing maximum clique algorithms (Debroni et al. 2011, Myrvold and Fowler 2013) since most heuristic clique algorithms fall short of the correct maximum clique order even for n=6.

A clique in G_n has size at most 2^n, and a clique attaining this bound disproves Keller's conjecture in dimension n and all higher dimensions (Corrádi and Szabó 1990). Lagarias and Shor (1992) found such a clique in dimension 10, and Mackey (2002) later found one in dimension eight. The generalized graphs needed to settle dimension seven are discussed under generalized Keller graph.

The clique numbers for the Keller graphs G_n with n=1, 2, ... are given by 1, 2, 5, 12, 28, 60, 124, 256, ... (OEIS A202604).

The chromatic, fractional chromatic numbers, and independence number of G_n are all 2^n for n>2 (W. Myrvold; S. Wagon, pers. comm., Jan. 22, 2013). The independence number for n=1, 2, ... are explicitly 4, 5, 8, 16, 32, 64, 128, 256, ... (OEIS A258935).

Jarnicki et al. (2016) showed that all Keller graphs are class 1, i.e., have edge chromatic number equal to their maximum vertex degree Delta.

Fung (2011) gives the Lovász numbers of the Keller graphs G_1, G_2, ..., as 4, 6, 28/3, 2^4, 2^5, ....

All connected Keller graphs are Hamiltonian (W. Myrvold; S. Wagon, pers. comm., Jan. 23, 2013) and Hamilton-connected (S. Wagon, pers. comm., Jan. 24, 2013).

See also

Clebsch Graph, Generalized Keller Graph, Keller's Conjecture, Maximum Clique

Explore with Wolfram|Alpha

References

Corrádi, K. and Szabó, S. "A Combinatorial Approach for Keller's Conjecture." Periodica Mathematica Hungarica. Journal of the János Bolyai Math. Soc. 21, 95-100, 1990.Debroni, J.; Eblen, J. D.; Langston, M. A.; Shor, P.; Myrvold, W.; and Weerapurage, D. "A Complete Resolution of the Keller Maximum Clique Problem." Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms. pp. 129-135, 2011.Fung, M. "The Lovász Number of the Keller Graphs." Master's thesis. Leiden, Netherlands: Mathematisch Instituut, Universiteit Leiden, 2011.House of Graphs. Keller Graphs. The Empty Graph on Four Vertices, Clebsch Graph, and Keller N=3.Jarnicki, W.; Myrvold, W.; Saltzman, P.; and Wagon, S. "Properties, Proved and Conjectured, of Keller, Mycielski, and Queen Graphs." 25 Jun 2016. https://arxiv.org/abs/1606.07918.Johnson, D. S. and Trick, M. A. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11-13, 1993. Boston, MA: Amer. Math. Soc., 1996.Lagarias, J. C. and Shor, P. W. "Keller's Cube-Tiling Conjecture Is False in High Dimensions." Bull. Amer. Math. Soc. 27, 279-283, 1992.Mackey, J. "Cube Tiling of Dimension Eight with No Facesharing." Disc. Comput. Geom. 28, 275-279, 2002.Myrvold, W. and Fowler, P. W. "Fast Enumeration of All Independent Sets up to Isomorphism." J. Comb. Math. Comb. Comput. 85, 173-194, 2013.Peron, O. "Über lückenlose ausfüllung des n-dimensionalen raumes durch kongruente würfel." Math. Z. 46, 1-26 and 161-180, 1940.Sloane, N. J. A. Sequences A202604 and A258935 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Keller Graph

Cite this as:

Weisstein, Eric W. "Keller Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/KellerGraph.html

Subject classifications