

A245762


Maximal number of edges in a C_4 free subgraph of the ncube.


1




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 5cube. Preprint.
H. Harborth and H. Nienborg, Maximum number of edges in a sixcube without fourcycles, Bulletin of the ICA 12 (1994) 5560


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 c4free subgraph of qn, J. Graph Theory 19 (1995) 1723
F. R. K. Chung, Subgraphs of a hypercube containing no small even cycles, J. Graph Theory 16 (1992) 273286
Paul Erdős Subgraphs of the cube without a 2kcycle
_Manfred Scheucher_ and _Paul Tabatabai_, Python Script


EXAMPLE

a(2) = 3 since the 2cube is the 4cycle and one needs to remove a single edge to get rid of all 4cycles.


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



