Crux and long cycles in graphs
We introduce a notion of the crux of a graph G, measuring the order of a smallest dense subgraph in G. This simple-looking notion leads to some generalisations of known results about cycles, offering an interesting paradigm of ‘replacing average degree by crux’. In particular, we prove that every gr...
| Main Authors: | , , , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2022
|