2025/04/25 by Derek G. Corneil, Feodor F. Dragan, Corneil, Derek G. +5 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2504.18508
In this paper we present various lower bound results on collective tree spanners and on spanners of bounded treewidth. A graph G is said to admit a system of μ collective additive tree c-spanners if there is a system \calT(G) of at most μ spanning trees of G such that for any two vertices u,v of G a tree T∈ \calT(G) exists such that the distance in T between u and v is at most c plus their distance in G. A graph G is said to admit an additive k-treewidth c-spanner if there is a spanning subgraph H of G with treewidth k such that for any pair of vertices u and v their distance in H is at most c plus their distance in G. Among other results, we show that: \bullet Any system of collective additive tree 1 -- spanners must have Ω(√[3]log n) spanning trees for some unit interval graphs; \bullet No system of a constant number of collective additive tree 2-spanners can exist for strongly chordal graphs; \bullet No system of a constant number of collective additive tree 3-spanners can exist for chordal graphs; \bullet No system of a constant number of collective additive tree c-spanners can exist for weakly chordal graphs as well as for outerplanar graphs for any constant c≥ 0; \bullet For any constants k ≥ 2 and c ≥ 1 there are graphs of treewidth k such that no spanning subgraph of treewidth k-1 can be an additive c-spanner of such a graph. All these lower bound results apply also to general graphs. Furthermore, they %results complement known upper bound results with tight lower bound results.