spanning trees


Kriesell's Conjecture ★★

Author(s): Kriesell

\begin{conjecture} Let $G$ be a graph and let $T\subseteq V(G)$ such that for any pair $u,v\in T$ there are $2k$ edge-disjoint paths from $u$ to $v$ in $G$. Then $G$ contains $k$ edge-disjoint trees, each of which contains $T$. \end{conjecture}

Keywords: Disjoint paths; edge-connectivity; spanning trees

spanning trees ★★

Author(s):

\begin{problem} Prove or disprove: Let $G$ be a graph with the minimum vertex degree at least 2; that is, $\delta(G)\geq 2$. Then there exists a spanning tree $T$ of $G$ such that for every support vertex $v$ in $T$ if $\deg_G(v)\geq 3$, then $\deg_T(v)\geq 3$. \end{problem}

Keywords: spanning trees

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

Author(s): Goldengorin

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.

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

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

\textbf{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?

Keywords: 1-trees; cycle; Hamitonian path; spanning trees

Syndicate content