Bisection of trees and sequences

N. Alon, Y. Caro, I. Krasikov

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

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).

Original languageEnglish (US)
Pages (from-to)3-7
Number of pages5
JournalDiscrete Mathematics
Volume114
Issue number1-3
DOIs
StatePublished - Apr 28 1993
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Bisection of trees and sequences'. Together they form a unique fingerprint.

  • Cite this