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

Hi,

Does anyone know that what is co spanning tree. If there are some good answers then it would be really good to have an example also.

Thanks

share|improve this question
1  
Can you explain in what context this term came up? –  Sebastian Oct 4 '11 at 14:11
3  
I would guess that it has to do with matroid duality, where the convention is to prefix everything in the dual with a co. So a cobasis is a basis in the dual, a cocircuit is a circuit in the dual, etc. If you regard a spanning tree as a basis for the graphic matroid, then a cospanning tree is just a basis in the dual, namely the complement of a spanning tree. I think it is time that someone invented the matroid term conut, so that a conut in the dual would be a... –  Tony Huynh Oct 4 '11 at 14:24
add comment

2 Answers

The paper here uses this name for the complement of a spanning tree, i.e. the set of edges which do not lie in some given spanning tree.

share|improve this answer
1  
That is also what I would expect it to mean. It is pretty much the same as Tony Huynh's comment: the complement of a spanning tree is a base for the dual matroid. If the given graph is planar, it is (the set of edges that dualize to) a spanning tree of the dual graph. –  David Eppstein Oct 7 '11 at 16:10
add comment

If $G = (V, E)$ has a spanning tree $T = (V, E_1)$, the cospanning tree of $T$ is a spanning subgraph of $G$, defined by $(V, E-E_1)$.

share|improve this answer
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.