Abstract | ||
---|---|---|
Let T be a spanning tree of a graph G. This paper is concerned with the following operation : we remove an edge e is an element of E(T) from T, and then add an edge f is an element of E(G) - E(T) so that T - e + f is a spanning tree of G. We refer to this operation of obtaining T - e + f from T as the transfer of e to f. We prove that if G is a 2-connected graph with \V(G)\ greater than or equal to 5, and if T-1 and T-2 are spanning trees of G which are not stars, then T-1 can be transformed into T-2 by repeated applications of a transfer of a nonpendant edge (an edge xy of a tree T is called a nonpendant edge of T if both of x and y have degree at least 2 in T). |
Year | Venue | Keywords |
---|---|---|
2001 | ARS COMBINATORIA | connected graph,spanning tree |
Field | DocType | Volume |
Discrete mathematics,Trémaux tree,Combinatorics,Tree (graph theory),Line graph,Graph factorization,Distance-hereditary graph,Spanning tree,Connected dominating set,Mathematics,Minimum spanning tree | Journal | 60 |
ISSN | Citations | PageRank |
0381-7032 | 0 | 0.34 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Takayuki Nakamura | 1 | 43 | 10.35 |
Kiyoshi Yoshimoto | 2 | 133 | 22.65 |