# Characterizing graphs with $k$ edge-disjoint minimum diameter spanning trees

Henneberg  and Laman  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õ . 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. ).

It is known that a minimum diameter spanning tree can also be found in polynomial time . 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$?

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

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

• 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? – user62562 Mar 23 '15 at 21:36
• @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? – Juho Mar 23 '15 at 21:59
• 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! – user62562 Mar 24 '15 at 10:05
• @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. – Juho Mar 24 '15 at 10:27