Isomorphic factorizations VIII: Bisectable trees
Tóm tắt
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.
Tài liệu tham khảo
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.