Premium
On the maximum number of edges in a c 4 ‐free subgraph of q n
Author(s) -
Brass Peter,
Harborth Heiko,
Nienborg Hauke
Publication year - 1995
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.3190190104
Subject(s) - combinatorics , mathematics , conjecture , graph , cube (algebra) , induced subgraph , discrete mathematics , vertex (graph theory)
For the maximum number f ( n ) of edges in a C 4 ‐free subgraph of the n ‐dimensional cube‐graph Q n we prove f ( n ) ≥ 1/2(n +√n)2 n−1 for n = 4 r , and f ( n ) ≥ 1/2(n +0.9√n)2 n−1 for all n ≥ 9. This disproves one version of a conjecture of P. Erdos. © 1995 John Wiley & Sons, Inc.