z-logo
Premium
Subgraphs of a hypercube containing no small even cycles
Author(s) -
Chung Fan R. K.
Publication year - 1992
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190160311
Subject(s) - hypercube , combinatorics , mathematics , integer (computer science) , cube (algebra) , enhanced data rates for gsm evolution , discrete mathematics , computer science , telecommunications , programming language
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 2 k ‐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 ).

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom