A counterexample for the proof of implication conjecture on independent spanning trees

作者：Gopalan Abishek; Ramasubramanian Srinivasan^*

来源：Information Processing Letters, 2013, 113(14-16): 522-526.

DOI：10.1016/j.ipl.2013.04.008

• Independent trees
• Spanning trees
• Three connectivity
• Graph algorithms

Khuller and Schieber (1992) in [1] developed a constructive algorithm to prove that the existence of k-vertex independent trees in a k-vertex connected graph implies the existence of k-edge independent trees in a k-edge connected graph. In this paper, we show a counterexample where their algorithm fails.

• 出版日期2013-8