Home » Subject » Graph Theory » Extremal G.T.
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.
1 comment

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options