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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.