Tree spanner

A tree k-spanner (or simply k-spanner) of a graph $G$ is a spanning subtree $T$ of $G$ in which the distance between every pair of vertices is at most $k$ times their distance in $G$.

Theorems

There are several known results about tree spanners. A significant number of these were produced in a paper entitled Tree Spanners written by mathematicians Leizhen Cai and Gordon Corneil. Some of the conclusion from that paper are listed below:

Theorem 1: If H is the spanning subgraph of a weighted graph $G=(V,E;w)$, then these statements are equivalent:

(a) H is a t-spanner of G for every pair of vertices of x and y of G. ${\displaystyle }$

(b) For every edge $xy$ in $V$, Failed to parse (syntax error): {\displaystyle d_H(x; y) ≤ t * d_G(x; y)} .

(c) For every edge xy in E\E(H), d_H(x; y) <= t * d_G(x; y).

(d) For every edge xy in E, d_H(x; y) <= t * w(xy).

(e) For every edge xy in E\E(H), d_H(x; y) <= t*w(xy).

Theorem 2: Let D and G be directed and undirected weighted graphs respectively, S and T be spanning trees of D and G,and Q be a quasitree of D. The following problems can be solved in O(m) time.

(a)Determine the stretch index of T.

(b)Is S a tree spanner?

(c)Is Q a quasitree spanner?

Theorem 3: Let H be a minimal 1-spanner of a weighted graph G, and let xy be an edge of G. The following statements are equivalent:

(a) The edge xy belongs to H

(b) For every vertex z in V\{x,y}, d_G(x; z) + d_G(z; y) > w(xy)

(c) The distance d_G-xy(x; y) > w(xy)

Theorem 4: The minimum (or optimal) 1-spanner of a weighted graph can be found in O(mn + n2log n) time.

Theorem 5: The tree 1-spanner of a weighted graph G is a minimum spanning tree. Furthermore, every tree 1-spanner admissible weighted graph contains a unique minimum spanning tree.

References

• Handke, Dagmar; Kortsarz, Guy (2000), "Tree spanners for subgraphs and related tree covering problems", Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000 Konstanz, Germany, June 15–17, 2000, Proceedings, Lecture Notes in Computer Science, vol. 1928, pp. 206–217, doi:10.1007/3-540-40064-8_20.