A graph G is called bisectable if it is an edge-disjoint union of two isomorphic subgraphs. We show that any tree T with e edges contains a bisectable subgraph with at least e-O(e/loglog e) edges. We also show that every forest of size e, each component of which is a star, contains a bisectable subgraph of size at least e-O(log2e).
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics