Subgraphs of a hypercube containing no small even cycles

1 July 1992

journal article
research article
Published by Wiley in Journal of Graph Theory

Vol. 16 (3) , 273-286
https://doi.org/10.1002/jgt.3190160311

Abstract

We investigate several Ramsey‐Turán type problems for subgraphs of a hypercube. We obtain upper and lower bounds for the maximum number of edges in a subgraph of a hypercube containing no four‐cycles or more generally, no 2k‐cycles C_2k. These extermal results imply, for example, the following Ramsey theorems for hypercubes: A hypercube can always be edge‐partitioned into four subgraphs, each of which contains no six‐cycle. However, for any integer t, if the n‐cube is edge‐partitioned into t sub‐graphs, then one of the subgraphs must contain an edight‐cycle, provided only than n is sufficiently large (depending only on t).

Keywords

This publication has 10 references indexed in Scilit:

Some of my favourite unsolved problems
Published by Cambridge University Press (CUP) ,2012
Cycles of even length in graphs
Published by Elsevier ,2004
Largest induced subgraphs of the n-cube that contain no 4-cycles
Journal of Combinatorial Theory, Series B, 1989
How robust is the n-cube?
Information and Computation, 1988
Reconfiguring a hypercube in the presence of faults
Published by Association for Computing Machinery (ACM) ,1987
The cube-connected cycles: a versatile network for parallel computation
Communications of the ACM, 1981
On Sets of Acquaintances and Strangers at any Party
The American Mathematical Monthly, 1959
On Sets of Acquaintances and Strangers at any Party
The American Mathematical Monthly, 1959
On the theory of graphs
Colloquium Mathematicum, 1954
On the structure of linear graphs
Bulletin of the American Mathematical Society, 1946