1
$\begingroup$

Given a connected undirected graph $G = (V,E)$, where each node has a minimum degree of $d$, find the minimum number $N$ such that there exists $N$ spanning trees $T_1, ..., T_N$, where for each node $v \in V$, either $v$ is an articulation point, i.e., the removal of $v$ disconnects the rest of the graph, or there exists some $1 \leq i \leq N$ such that $v$ is a leaf in tree $T_i$.

$\endgroup$
7
  • 2
    $\begingroup$ You want your graph not to have any cut vertices for this to be possible. Other than that, it's unclear what answer you are looking for. Do you want to bound $N$ in terms of some other data (minimum degree etc.)? Otherwise a simple answer is that for a 2-vertex connected graph $N\le |V|+1/2$, and equality is achieved for odd cycles. $\endgroup$ Jun 8, 2012 at 6:43
  • $\begingroup$ That should have been $N\le (|V|+1)/2$ $\endgroup$ Jun 8, 2012 at 6:43
  • $\begingroup$ Thanks for your answer. Yes, actually I want to bound the minimum degree of a node. Except for articulation points which are impossible to cover, all the rest should be covered by at least one tree. Please see the updated problem description. $\endgroup$
    – Hongyang
    Jun 8, 2012 at 7:39
  • $\begingroup$ If you have subsets $V_1, V_2, ..., V_k$ of $V$ such that $G-E(V_k)$ is connected for each $k$ and the $V_j$ cover $V$ then $N \leq k$. $\endgroup$
    – hbm
    Jun 8, 2012 at 21:59
  • $\begingroup$ I meant $G-E(V_j)$ is connected for each $j \leq k$. $\endgroup$
    – hbm
    Jun 8, 2012 at 23:20

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.