Back to Search
Start Over
A parity theorem about trees with specified degrees.
- Source :
-
Discrete Applied Mathematics . Dec2021, Vol. 305, p48-55. 8p. - Publication Year :
- 2021
-
Abstract
- Carsten Thomassen and I proved that in any graph G , the number of cycles containing a specified edge as well as all the vertices of odd degree is odd if and only if G is eulerian. Where all vertices have even degree this is a theorem of Shunichi Toida and where all vertices have odd degree it is Andrew Thomason's extension of Smith's Theorem. Our proof was not algorithmic. In this paper, I extend Thomason's algorithm to one which, in a non-eulerian graph, finds a second cycle containing a specified edge and all the odd-degree vertices. Kenneth Berman extended Thomason's Theorem to spanning trees: he proved that if T is a spanning tree such that the degree of every vertex in G − E (T) is odd, then there is an even number of spanning trees of G with the same degree as T at each vertex. In this paper, I give a common generalization of all of these theorems to a parity theorem about "good" trees in general graphs. My proof provides an algorithm for finding a second "good" tree. [ABSTRACT FROM AUTHOR]
- Subjects :
- *ALGORITHMS
*TREE graphs
*TREES
*SPANNING trees
*GENERALIZATION
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 305
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 153070124
- Full Text :
- https://doi.org/10.1016/j.dam.2021.08.017