Largest induced subgraphs of the n-cube that contain no 4-cycles (Q580365)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Largest induced subgraphs of the n-cube that contain no 4-cycles |
scientific article |
Statements
Largest induced subgraphs of the n-cube that contain no 4-cycles (English)
0 references
1989
0 references
Every induced subgraph of the n-cube, \(Q_ n\), with more than \(\lceil 2^{n+1}/3\rceil\) vertices is shown to contain a 4-cycle; this bound is sharp. The extremal graphs are characterized as translations of a specific subgraph of \(Q_ n\).
0 references
n-cube
0 references
cycle
0 references
extremal graphs
0 references
