Packing tree factors in random and pseudo-random graphs

Deepak Bal, Alan Frieze, Michael Krivelevich, Po Shen Loh

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

For a fixed graph H with t vertices, an H-factor of a graph G with n vertices, where t divides n, is a collection of vertex disjoint (not necessarily induced) copies of H in G covering all vertices of G. We prove that for a fixed tree T on t vertices and ε > 0, the random graph Gn,p, with n a multiple of t, with high probability contains a family of edge-disjoint T-factors covering all but an ε-fraction of its edges, as long as ε4np ≫ log2 n. Assuming stronger divisibility conditions, the edge probability can be taken down to p >. A similar packing result is proved also for pseudo- random graphs, defined in terms of their degrees and co-degrees.

Original languageEnglish
JournalElectronic Journal of Combinatorics
Volume21
Issue number2
StatePublished - 16 Apr 2014

Fingerprint

Factor tree
Random Graphs
Packing
Disjoint
Covering
Divisibility
Graph in graph theory
Divides
Vertex of a graph

Keywords

  • Packing
  • Pseudo-random graphs
  • Random graphs
  • Tree factors

Cite this

Bal, Deepak ; Frieze, Alan ; Krivelevich, Michael ; Loh, Po Shen. / Packing tree factors in random and pseudo-random graphs. In: Electronic Journal of Combinatorics. 2014 ; Vol. 21, No. 2.
@article{7b1ef21713cd4d4194c259b2c9cb4cc6,
title = "Packing tree factors in random and pseudo-random graphs",
abstract = "For a fixed graph H with t vertices, an H-factor of a graph G with n vertices, where t divides n, is a collection of vertex disjoint (not necessarily induced) copies of H in G covering all vertices of G. We prove that for a fixed tree T on t vertices and ε > 0, the random graph Gn,p, with n a multiple of t, with high probability contains a family of edge-disjoint T-factors covering all but an ε-fraction of its edges, as long as ε4np ≫ log2 n. Assuming stronger divisibility conditions, the edge probability can be taken down to p >. A similar packing result is proved also for pseudo- random graphs, defined in terms of their degrees and co-degrees.",
keywords = "Packing, Pseudo-random graphs, Random graphs, Tree factors",
author = "Deepak Bal and Alan Frieze and Michael Krivelevich and Loh, {Po Shen}",
year = "2014",
month = "4",
day = "16",
language = "English",
volume = "21",
journal = "Electronic Journal of Combinatorics",
issn = "1077-8926",
publisher = "Electronic Journal of Combinatorics",
number = "2",

}

Bal, D, Frieze, A, Krivelevich, M & Loh, PS 2014, 'Packing tree factors in random and pseudo-random graphs', Electronic Journal of Combinatorics, vol. 21, no. 2.

Packing tree factors in random and pseudo-random graphs. / Bal, Deepak; Frieze, Alan; Krivelevich, Michael; Loh, Po Shen.

In: Electronic Journal of Combinatorics, Vol. 21, No. 2, 16.04.2014.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Packing tree factors in random and pseudo-random graphs

AU - Bal, Deepak

AU - Frieze, Alan

AU - Krivelevich, Michael

AU - Loh, Po Shen

PY - 2014/4/16

Y1 - 2014/4/16

N2 - For a fixed graph H with t vertices, an H-factor of a graph G with n vertices, where t divides n, is a collection of vertex disjoint (not necessarily induced) copies of H in G covering all vertices of G. We prove that for a fixed tree T on t vertices and ε > 0, the random graph Gn,p, with n a multiple of t, with high probability contains a family of edge-disjoint T-factors covering all but an ε-fraction of its edges, as long as ε4np ≫ log2 n. Assuming stronger divisibility conditions, the edge probability can be taken down to p >. A similar packing result is proved also for pseudo- random graphs, defined in terms of their degrees and co-degrees.

AB - For a fixed graph H with t vertices, an H-factor of a graph G with n vertices, where t divides n, is a collection of vertex disjoint (not necessarily induced) copies of H in G covering all vertices of G. We prove that for a fixed tree T on t vertices and ε > 0, the random graph Gn,p, with n a multiple of t, with high probability contains a family of edge-disjoint T-factors covering all but an ε-fraction of its edges, as long as ε4np ≫ log2 n. Assuming stronger divisibility conditions, the edge probability can be taken down to p >. A similar packing result is proved also for pseudo- random graphs, defined in terms of their degrees and co-degrees.

KW - Packing

KW - Pseudo-random graphs

KW - Random graphs

KW - Tree factors

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

M3 - Article

AN - SCOPUS:84898963331

VL - 21

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

SN - 1077-8926

IS - 2

ER -