Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$.

share|improve this question
2  
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. –  Gjergji Zaimi Jun 8 '12 at 6:43
    
That should have been $N\le (|V|+1)/2$ –  Gjergji Zaimi Jun 8 '12 at 6:43
    
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. –  Hongyang Jun 8 '12 at 7:39
    
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$. –  hbm Jun 8 '12 at 21:59
    
I meant $G-E(V_j)$ is connected for each $j \leq k$. –  hbm Jun 8 '12 at 23:20
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.