Families of Trees Decompose the Random Graph in an Arbitrary Way

DOI10.1017/S096354830400639XMaRDI QIDQ4650645zbMATH OpenOpenAlexFDO

Authors Raphael Yuster

Publication date 18 February 2005

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0210339

zbMATH Keywords

decomposablerandom graphthresholdtotally decomposable

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Let $F=H_1,\mathrm{...},H_k$ be a family of graphs. A graph $G$ with $m$ edges is called {em totally $F$-decomposable} if for {em every} linear combination of the form $alph{a}_{1}e(H_1)+\mathrm{...}+alph{a}_{k}e(H_k)=m$ where each $alph{a}_i$ is a nonnegative integer, there is a coloring of the edges of $G$ with $alph{a}_1+\mathrm{...}+alph{a}_k$ colors such that exactly $alph{a}_i$ color classes induce each a copy of $H_i$, for $i=1,\mathrm{...},k$. We prove that if $F$ is any fixed family of trees then $logn/n$ is a sharp threshold function for the property that the random graph $G(n,p)$ is totally $F$-decomposable. In particular, if $H$ is a tree, then $logn/n$ is a sharp threshold function for the property that $G(n,p)$ contains $lfloore(G)/e(H)floor$ edge-disjoint copies of $H$.

Recommendations

• Decomposing almost complete graphs by random trees
• Decomposing almost complete graphs by random trees
• Almost every tree with \(m\) edges decomposes \(K_{2m,2m}\)
• The decomposition of trees into subtrees
• Decompositions of graphs into trees

Cited in

(3)

• The decomposition of trees into subtrees
• Combinatorial and computational aspects of graph packing and graph decomposition
• Decomposing almost complete graphs by random trees

This page was built for publication: Families of Trees Decompose the Random Graph in an Arbitrary Way

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