Bisection of trees and sequences

N. Alon; Y. Caro; I. Krasikov

doi:10.1016/0012-365X(93)90350-3

Bisection of trees and sequences

N. Alon, Y. Caro, I. Krasikov

Research output: Contribution to journal › Article › peer-review

4 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(log²e).

Original language	English (US)
Pages (from-to)	3-7
Number of pages	5
Journal	Discrete Mathematics
Volume	114
Issue number	1-3
DOIs	https://doi.org/10.1016/0012-365X(93)90350-3
State	Published - Apr 28 1993
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/0012-365X(93)90350-3

Cite this

@article{26e5d49fe5404ba5a1ccf6db1b4f398e,

title = "Bisection of trees and sequences",

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

author = "N. Alon and Y. Caro and I. Krasikov",

year = "1993",

month = apr,

day = "28",

doi = "10.1016/0012-365X(93)90350-3",

language = "English (US)",

volume = "114",

pages = "3--7",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - Bisection of trees and sequences

AU - Alon, N.

AU - Caro, Y.

AU - Krasikov, I.

PY - 1993/4/28

Y1 - 1993/4/28

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

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

UR - http://www.scopus.com/inward/record.url?scp=38249003411&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38249003411&partnerID=8YFLogxK

U2 - 10.1016/0012-365X(93)90350-3

DO - 10.1016/0012-365X(93)90350-3

M3 - Article

AN - SCOPUS:38249003411

SN - 0012-365X

VL - 114

SP - 3

EP - 7

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Bisection of trees and sequences

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this