English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We wish to bring attention to a natural but slightly hidden problem, posed byErd\H{o}s and Ne\v{s}et\v{r}il in the late 1980s, an edge version of thedegree--diameter problem. Our main result is that, for any graph of maximumdegree $\Delta$ with more than $1.5 \Delta^t$ edges, its line graph must havediameter larger than $t$. In the case where the graph contains no cycle oflength $2t+1$, we can improve the bound on the number of edges to one that isexact for $t\in\{1,2,3,4,6\}$. In the case $\Delta=3$ and $t=3$, we obtain anexact bound. Our results also have implications for the related problem ofbounding the distance-$t$ chromatic index, $t>2$; in particular, for this weobtain an upper bound of $1.941\Delta^t$ for graphs of large enough maximumdegree $\Delta$, markedly improving upon earlier bounds for this parameter.

Maximising line subgraphs of diameter at most $t$