OFFSET
1,2
COMMENTS
This is related to the famous conjecture of Erdős (see Erdős link).
REFERENCES
M. R. Emamy, K. P. Guan and I. J. Dejter, On fault tolerance in a 5-cube. Preprint.
H. Harborth and H. Nienborg, Maximum number of edges in a six-cube without four-cycles, Bulletin of the ICA 12 (1994) 55-60
LINKS
P. Brass, H. Harborth and H. Nienborg, On the maximum number of edges in a c4-free subgraph of qn, J. Graph Theory 19 (1995) 17-23
F. R. K. Chung, Subgraphs of a hypercube containing no small even cycles, J. Graph Theory 16 (1992) 273-286
Paul Erdős, Subgraphs of the cube without a 2k-cycle
Manfred Scheucher and Paul Tabatabai, Python Script
EXAMPLE
a(2) = 3 since the 2-cube is the 4-cycle and one needs to remove a single edge to get rid of all 4-cycles.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Jernej Azarija, Jul 31 2014
EXTENSIONS
a(6) from Manfred Scheucher and Paul Tabatabai, Jul 23 2015
STATUS
approved