Largest induced subgraphs of the n-cube that contain no 4-cycles (Q580365): Difference between revisions
From MaRDI portal
Changed an Item |
Added link to MaRDI item. |
||
| links / mardi / name | links / mardi / name | ||
Revision as of 07:27, 30 January 2024
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
