login
A245762
Maximal number of edges in a C_4 free subgraph of the n-cube.
1
1, 3, 9, 24, 56, 132
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
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
Sequence in context: A227018 A244504 A085739 * A291706 A089830 A258111
KEYWORD
nonn,more
AUTHOR
Jernej Azarija, Jul 31 2014
EXTENSIONS
a(6) from Manfred Scheucher and Paul Tabatabai, Jul 23 2015
STATUS
approved