Home » Subject » Graph Theory » Extremal G.T.

What is the smallest number of disjoint spanning trees made a graph Hamiltonian

Importance: Medium ✭✭
Author(s): Goldengorin
Subject: Graph Theory
» Extremal Graph Theory
Keywords: 1-trees
cycle
Hamitonian path
spanning trees
Recomm. for undergrads: no
Posted by: boris
on: September 10th, 2007

We are given a complete simple undirected weighted graph $ G_1=(V,E) $ and its first arbitrary shortest spanning tree $ T_1=(V,E_1) $. We define the next graph $ G_2=(V,E\setminus E_1) $ and find on $ G_2 $ the second arbitrary shortest spanning tree $ T_2=(V,E_2) $. We continue similarly by finding $ T_3=(V,E_3) $ on $ G_3=(V,E\setminus \cup_{i=1}^{2}E_i) $, etc. Let k be the smallest number of disjoint shortest spanning trees as defined above and let $ T^{k}=(V,\cup_{i=1}^{k}E_i) $ be the graph obtained as union of all $ k $ disjoint trees.

Question 1. What is the smallest number of disjoint spanning trees creates a graph $ T^{k} $ containing a Hamiltonian path.

Question 2. What is the smallest number of disjoint spanning trees creates a graph $ T^{k} $ containing a shortest Hamiltonian path?

Questions 3 and 4. Replace in questions 1 and 2 a shortest spanning tree by a 1-tree. What is the smallest number of disjoint 1-trees creates a Hamiltonian graph? What is the smallest number of disjoint 1-trees creates a graph containing a shortest Hamiltonian cycle?

These questions are induced by the following paper Chrobak and Poljak. On common edges in optimal solutions to travelling salesman and other optimization problems, Discrete Applied Mathematics 20 (1988) 101-111.

Bibliography

M. Chrobak and S. Poljak. On common edges in optimal solutions to travelling salesman and other optimization problems, Discrete Applied Mathematics 20 (1988) 101-111.


* indicates original appearance(s) of problem.
add new comment

Is this statement correct?

On September 10th, 2007 mdevos says:

Unless I am mistaken, it appears that there does not exist any $ k $ for which any of the above problems has a positive solution. For instance, let $ G $ be the complete graph with vertex set $ V = \{1,\ldots,6k\} $, and define $ C $ to be the edge-cut of $ G $ consisting of all edges between $ \{1,2,\ldots,2k\} $ and $ \{2k+1,2k+2,\ldots,6k\} $. Now define a weighting of $ G $ by assigning each edge in $ C $ weight 1 and every other edge weight 2. So, the subgraph $ (V,C) $ (consisting of all edges of weight 1) is isomorphic to $ K_{2k,4k} $ - and since $ K_{2k,4k} $ has $ k $ edge-disjoint spanning trees (by the Nash-Williams theorem, say), our procedure may well choose trees $ T_1,T_2,\ldots,T_k $ so that all of the edges in all of these graphs are in $ C $. But then $ T^k $ will not have a Hamiltonian path since it is a subgraph of $ (V,C) \cong K_{2k,4k} $.

Of course, we may modify the edge weights here so that the procedure is forced to choose $ T_1,\ldots,T_k $ so that all of these trees have their edges in $ C $.

reply

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.