Isomorphic factorizations VIII: Bisectable trees

Trees (05C05) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

A graph is t-factorable if its edges can be partitioned into t copies of a common factor subgraph. When the original graph is a tree T the common factor must, of course, be a forest, but if the factor S also happens to be a tree we say that T is t-sectable. The authors show that given T and t there is at most one candidate for S. This fact leads to a linear time and space algorithm for determining the t-sectability of T. Furthermore, for \(t=2\) a bisectable tree T also has a unique bisection, but for \(t>2\) there can be inequivalent t-sections even though all use the same factor S. This extra structural knowledge for bisections allows the authors to use standard enumeration techniques to count the number of bisectable trees and find asymptotic estimates. The reader should be alerted that in the final half page the letter n appears in several formulas without explanation, but it appears that n is identical to p. To contrast the algorithmic difficult of t-factorization as opposed to t-sectability, in the next article in this series, Isomorphic Factorizations IX: Even Trees (to appear), \textit{R. L. Graham} and \textit{R. W. Robinson} show that deciding whether a tree is 2-factorable is NP-hard.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Isomorphic factorizations VIII: Bisectable trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1060225)