On a problem of Duke-Erdos-Rodl on cycle-connected subgraphs
| dc.creator | Fox, Jacob | |
| dc.creator | Sudakov, Benny | |
| dc.date | 2007-06-13 | |
| dc.date | 2007-11-11 | |
| dc.date.accessioned | 2026-07-07T08:41:42Z | |
| dc.date.available | 2026-07-07T08:41:42Z | |
| dc.description | In this short note, we prove that for β< 1/5 every graph G with n vertices and n^{2-β} edges contains a subgraph G' with at least cn^{2-2β} edges such that every pair of edges in G' lie together on a cycle of length at most 8. Moreover edges in G' which share a vertex lie together on a cycle of length at most 6. This result is best possible up to the constant factor and settles a conjecture of Duke, Erdos, and Rodl. | |
| dc.description | 7 pages | |
| dc.identifier | https://arxiv.org/abs/0706.1920 | |
| dc.identifier | http://arxiv.org/abs/0706.1920 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/141757 | |
| dc.subject | Combinatorics | |
| dc.subject | Number Theory | |
| dc.subject | 05C35, 05C40, 11P70 | |
| dc.title | On a problem of Duke-Erdos-Rodl on cycle-connected subgraphs | |
| dc.type | text |