Abstract
A tree is called even if its line set can be partitioned into two isomorphic subforests; it is bisectable if these forests are trees. The problem of deciding whether a given tree is even is known (Graham and Robinson) to be NP-hard. That for bisectability is now shown to have a polynomial time algorithm. This result is contained in the proof of a theorem which shows that if a treeS is bisectable then there is a unique treeT that accomplishes the bipartition. With the help of the uniqueness ofT and the observation that the bisection ofS into two copies ofT is unique up to isomorphism, we enumerate bisectable trees.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Y. Caro andJ. Schönheim, Decomposition of trees into isomorphic subtrees,Ars Combin.9 (1980), 119–130.
R. L. Graham andR. W. Robinson, Isomorphic factorizations IX: Even trees,to appear.
F. Harary,Graph Theory, Addison-Wesley, Reading (1969).
F. Harary andE. M. Palmer,Graphical Enumeration, Academic, New York (1973).
F. Harary andE. M. Palmer, The probability that a point of a tree is fixed,Math. Proc. Cambridge Philos. Soc.85 (1979), 407–415.
F. Harary andR. W. Robinson, Generalized Ramsey theory IX: Isomorphic factorizations IV: Isomorphic Ramsey numbers,Pacific J. Math.80 (1979), 435–441.
F. Harary, R. W. Robinson andA. J. Schwenk, Twenty-step algorithm for determining the asymptotic number of trees of various species,J. Austral. Math. Soc.20 (1975), 483–503.
F. Harary, R. W. Robinson andN. C. Wormald, Isomorphic factorizations I: Complete graphs,Trans. Amer. Math. Soc.242 (1978), 243–260.
F. Harary, R. W. Robinson andN. C. Wormald, Isomorphic factorizations III: Complete multipartite graphs,Springer Lecture Notes Math.686 (1978), 47–54.
F. Harary, R. W. Robinson andN. C. Wormald, Isomorphic factorizations V: Directed graphs,Mathematika25 (1978), 279–285.
F. Harary andW. D. Wallis, Isomorphic factorizations II: Combinatorial designs,Congressus Numerantium19 (1978), 13–28.
J. E. Hopcroft andR. E. Tarjan, Isomorphism of planar graphs,Complexity of Computer Computations (R.E. Miller and J. W. Thatcher, eds.) Plenum, New York (1972), 131–152.
R. W. Robinson, Isomorphic factorization VI: Automorphisms,Springer Lecture Notes Math.748 (1979), 127–136.
R. W. Robinson andA. J. Schwenk, The distribution of points in a large random tree,Discrete Math.12 (1975), 359–372.
N. C. Wormald, Isomorphic factorization VII: Regular graphs and tournaments,J. Graph. Theory8 (1984), 117–122.
Author information
Authors and Affiliations
Additional information
Visiting Professor, University of Newcastle, 1976 and 1977 when this work was begun.
Visiting Scholar, University of Michigan, 1981–82 on leave from Newcastle University (Australia) when this work was completed. The research was supported by grants from the Australian Research Grants Commission. The computing reported herein was performed by A. Nymeyer.