On the maximum number of edges in a c4‐free subgraph of qn
- 1 January 1995
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 19 (1) , 17-23
- https://doi.org/10.1002/jgt.3190190104
Abstract
For the maximum number f(n) of edges in a C4‐free subgraph of the n‐dimensional cube‐graph Qn we prove f(n) ≥ 1/2(n +√n)2n−1 for n = 4r, and f(n) ≥ 1/2(n +0.9√n)2n−1 for all n ≥ 9. This disproves one version of a conjecture of P. Erdos. © 1995 John Wiley & Sons, Inc.Keywords
This publication has 3 references indexed in Scilit:
- Highly Symmetric Subgraphs of HypercubesJournal of Algebraic Combinatorics, 1993
- Subgraphs of a hypercube containing no small even cyclesJournal of Graph Theory, 1992
- How robust is the n-cube?Information and Computation, 1988