Henneberg [1] and Laman [2] characterized graphs which have, after adding any edge, 2 edge-disjoint spanning trees. This was generalized to $k$ edge-disjoint spanning trees by Frank and Szegõ [3]. They also gave a characterization of graphs which have $k$ edge-disjoint spanning trees after the deletion of any edge of them. Furthermore, it is known that $k$ edge-disjoint spanning trees can be found in polynomial time (see e.g. [4]).

It is known that a minimum diameter spanning tree can also be found in polynomial time [5]. My guess is that we can also find $k$ minimum diameter spanning trees efficiently. But is a characterization of graphs that have $k$ edge-disjoint minimum diameter spanning trees known, even for $k=2$?

[1] Henneberg, Lebrecht. Die graphische Statik der starren Systeme. Vol. 31. BG Teubner, 1911.

[2] Laman, Gerard. "On graphs and rigidity of plane skeletal structures." Journal of Engineering mathematics 4.4 (1970): 331-340.

[3] Frank, András, and László Szego. "Constructive characterizations for packing and covering with trees." Discrete Applied Mathematics 131.2 (2003): 347-371.

[4] Roskind, James, and Robert E. Tarjan. "A note on finding minimum-cost edge-disjoint spanning trees." Mathematics of Operations Research 10.4 (1985): 701-708.

[5] Hassin, Refael, and Arie Tamir. "On the minimum diameter spanning tree problem." Information processing letters 53.2 (1995): 109-111.

  • $\begingroup$ As far as I know, this is an open problem. However it is tempting to suggest that it isn't too hard, especially for k=2. Have you tried directly using Tay's (or Fekete and Szego's or Frank and Szego's) recursive construction and arguing about the diameter as you go? $\endgroup$ – user62562 Mar 23 '15 at 21:36
  • $\begingroup$ @user62562 As far as I know, it is indeed open. I asked Frank about it, and he thought it was open as well. To be honest no I didn't - do you have a reference for Tay's construction? $\endgroup$ – Juho Mar 23 '15 at 21:59
  • $\begingroup$ It's been a while since I read it but I think it's this one: Tiong-Seng Tay, Henneberg’s method for bar and body frameworks, Structural Topology, 17:53–58, 1991. He proves a recursive characterisation for graphs that decompose into k edge-disjoint spanning trees and then uses that to prove a characterisation of rigidity for body-bar frameworks. For k=2 I recall the proof being reasonably elementary. I should admit I've never thought about minimum degree spanning trees so I have no real intuition for them, otherwise I'd have a go myself! $\endgroup$ – user62562 Mar 24 '15 at 10:05
  • $\begingroup$ @user62562 Oh, but I should mention that there is a characterization of graphs that have diameter-preserving spanning trees by Buckley and Lewinter. So this needs to satisfied at least. $\endgroup$ – Juho Mar 24 '15 at 10:27

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.