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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A tree $t$-spanner of a graph $G$ is a spanning tree $T$ in which thedistance between any two adjacent vertices of $G$ is at most $t$. The smallest$t$ for which $G$ has a tree $t$-spanner is called tree stretch index. The$t$-admissibility problem aims to decide whether the tree stretch index is atmost $t$. Regarding its optimization version, the smallest $t$ for which $G$ is$t$-admissible is the stretch index of $G$, denoted by $\sigma_T(G)$. Given agraph with $n$ vertices and $m$ edges, the recognition of $2$-admissible graphscan be done $O(n+m)$ time, whereas $t$-admissibility is NP-complete for$\sigma_T(G) \leq t$, $t \geq 4$ and deciding if $t = 3$ is an open problem,for more than 20 years. Since the structural knowledge of classes can bedeterminant to classify $3$-admissibility's complexity, in this paper wepresent simpler and faster algorithms to check $2$ and $3$-admissibility forfamilies of graphs with few $P_4$'s and $(k,\ell)$-graphs. Regarding$(0,\ell)$-graphs, we present lower and upper bounds for the stretch index ofthese graphs and characterize graphs whose stretch indexes are equal to theproposed upper bound. Moreover, we prove that $t$-admissibility is NP-completeeven for line graphs of subdivided graphs.

Simpler and efficient characterizations of tree t-spanners for graphs with few P4's and (k, l)-graphs