login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A245762 Maximal number of edges in a C_4 free subgraph of the n-cube. 1
1, 3, 9, 24, 56, 132 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 26 18:08 EDT 2020. Contains 334630 sequences. (Running on oeis4.)