On induced subgraphs of the cube

F. R.K. Chung; Zoltán Füredi; R. L. Graham; P. Seymour

doi:10.1016/0097-3165(88)90034-9

On induced subgraphs of the cube

F. R.K. Chung, Zoltán Füredi, R. L. Graham, P. Seymour

Research output: Contribution to journal › Article › peer-review

43 Scopus citations

Abstract

Consider the usual graph Qⁿ defined by the n-dimensional cube (having 2ⁿ vertices and n2^{n - 1} edges). We prove that if G is an induced subgraph of Qⁿ with more than 2^{n - 1} vertices then the maximum degree in G is at least ( 1 2 - o(1)) log n. On the other hand, we construct an example which shows that this is not true for maximum degree larger than.

Original language	English (US)
Pages (from-to)	180-187
Number of pages	8
Journal	Journal of Combinatorial Theory, Series A
Volume	49
Issue number	1
DOIs	https://doi.org/10.1016/0097-3165(88)90034-9
State	Published - Sep 1988
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/0097-3165(88)90034-9

Cite this

@article{3cbadb3b066a4229bb7bd82dca593c84,

title = "On induced subgraphs of the cube",

abstract = "Consider the usual graph Qn defined by the n-dimensional cube (having 2n vertices and n2n - 1 edges). We prove that if G is an induced subgraph of Qn with more than 2n - 1 vertices then the maximum degree in G is at least ( 1 2 - o(1)) log n. On the other hand, we construct an example which shows that this is not true for maximum degree larger than.",

author = "Chung, {F. R.K.} and Zolt{\'a}n F{\"u}redi and Graham, {R. L.} and P. Seymour",

year = "1988",

month = sep,

doi = "10.1016/0097-3165(88)90034-9",

language = "English (US)",

volume = "49",

pages = "180--187",

journal = "Journal of Combinatorial Theory, Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - On induced subgraphs of the cube

AU - Chung, F. R.K.

AU - Füredi, Zoltán

AU - Graham, R. L.

AU - Seymour, P.

PY - 1988/9

Y1 - 1988/9

N2 - Consider the usual graph Qn defined by the n-dimensional cube (having 2n vertices and n2n - 1 edges). We prove that if G is an induced subgraph of Qn with more than 2n - 1 vertices then the maximum degree in G is at least ( 1 2 - o(1)) log n. On the other hand, we construct an example which shows that this is not true for maximum degree larger than.

AB - Consider the usual graph Qn defined by the n-dimensional cube (having 2n vertices and n2n - 1 edges). We prove that if G is an induced subgraph of Qn with more than 2n - 1 vertices then the maximum degree in G is at least ( 1 2 - o(1)) log n. On the other hand, we construct an example which shows that this is not true for maximum degree larger than.

UR - http://www.scopus.com/inward/record.url?scp=38249028422&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38249028422&partnerID=8YFLogxK

U2 - 10.1016/0097-3165(88)90034-9

DO - 10.1016/0097-3165(88)90034-9

M3 - Article

AN - SCOPUS:38249028422

SN - 0097-3165

VL - 49

SP - 180

EP - 187

JO - Journal of Combinatorial Theory, Series A

JF - Journal of Combinatorial Theory, Series A

IS - 1

ER -

On induced subgraphs of the cube

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this