On a property of the n-dimensional cube

2011/10/27 by Rafayel R. Kamalian, Rafayel Kamalian, Kamalian, Rafayel +3
Computer Science · Engineering · Mathematics · #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #cs.DM #graph theory and CDMA systems #math.CO

paper · pdf · doi:10.48550/arxiv.1110.6010

2 pages, no figures

arxiv created 2011/10/27 · arxiv updated 2011/10/28

Abstract

We show that in any subset of the vertices of n-dimensional cube that contains at least 2^n-1+1 vertices (n≥ 4), there are four vertices that induce a claw, or there are eight vertices that induce the cycle of length eight.

Related

• On Tomaszewski's Cube Vertices Problem
• On the Erdős-Gyárfás conjecture in claw-free graphs
• Four Cubes
• On a theorem of Erdős and Simonovits on graphs not containing the cube
• Cubicity of interval graphs and the claw number