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

1, 3, 9, 24, 56, 132

Offset: 1

Author

Jernej Azarija, Jul 31 2014

Keywords

• nonn
• more
• changed

Comments

This is related to the famous conjecture of Erdős (see Erdős link).

Examples

			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.
		

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

• Thomas Bloom, Subgraphs of the cube without a 2k-cycle, Erdős Problems.
• 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

Extensions

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