Largest induced subgraphs of the n-cube that contain no 4-cycles (Q580365): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Q3097395 / rank | |||
Normal rank | |||
Latest revision as of 11:18, 18 June 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
