A245762 Maximal number of edges in a C_4 free subgraph of the n-cube.

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

Table of n, a(n) for n=1..6.

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

Sequence in context: A227018 A244504 A085739 * A291706 A089830 A258111

Adjacent sequences: A245759 A245760 A245761 * A245763 A245764 A245765

Keyword

nonn,more

Author

Jernej Azarija, Jul 31 2014

Extensions

a(6) from Manfred Scheucher and Paul Tabatabai, Jul 23 2015

Status

approved