bispanning graphs

Hello,

I recently stumbled upon bispanning graphs.
A bispanning graph is a graph G=(V,E) so that E can be partitoned into
two sets P and Q so that (V,P) and (V,Q) are spanning trees of G.

Asking google for "bispanning graph" gives only a few results at the
local chair. So either this graph class is actually quite exotic, or it
is usually know by a different name.

Does anyone know about this kind of graphs?
What is the usual name for it?

Thanks,
Michael

In article <g934tl$738$1@news.in.tum.de>,
Michael Schnupp <michas@nurfuerspam.de> wrote:
>I recently stumbled upon bispanning graphs.
>A bispanning graph is a graph G=(V,E) so that E can be partitoned into
>two sets P and Q so that (V,P) and (V,Q) are spanning trees of G.
>
>Asking google for "bispanning graph" gives only a few results at the
>local chair. So either this graph class is actually quite exotic, or it
>is usually know by a different name.
>
>Does anyone know about this kind of graphs?
>What is the usual name for it?

I haven't heard of the term "bispanning graph" before. However, a
MathSciNet search for "two edge-disjoint spanning trees" yields 15 hits.
Several of the papers are extensions of Jaeger's result [J. Graph Theory
3 (1979), no. 1, 91-93] that if a graph has two edge-disjoint spanning
trees, then it is super-Eulerian, i.e., it has a spanning closed trail.
Others are concerned with algorithmic questions, e.g., Tarjan [Acta
Informat. 6 (1976), no. 2, 171-185] gives an algorithm for finding two
edge-disjoint spanning trees rooted at a fixed vertex of a directed graph.

Searching just for "edge-disjoint spanning trees" yields 61 hits, the
oldest one being a paper by Nash-Williams that proves that a graph G
has k disjoint spanning trees if and only if for any partition of the
vertices of G into p sets the number of edges joining two different sets
of the partition is at least k(p-1) (this result is also due independently
to Tutte).

I also found two papers that use the term "block matroid" for a matroid
that is the disjoint union of two bases.

So it seems that your graphs have been considered indirectly before, but
haven't acquired a standard name.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences