Decomposition of random graphs into complete bipartite graphs

DOI10.1137/140960888zbMATH Open1330.05124arXiv1402.0860OpenAlexW2962859276MaRDI QIDQ5744698FDOQ5744698

Authors: Xing Peng, Fan Chung 

Publication date: 19 February 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We consider the problem of partitioning the edge set of a graph $G$ into the minimum number $au(G)$ of edge-disjoint complete bipartite subgraphs. We show that for a random graph $G$ in $G(n,p)$, for $p$ is a constant no greater than $1/2$, almost surely $au(G)$ is between $n-c(l{n}_{1/p}n{)}^{3+epsilon}$ and $n-2l{n}_{1/(1-p)}n$ for any positive constants $c$ and $epsilon$.

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

Recommendations

• Bipartite decomposition of random graphs
• scientific article; zbMATH DE number 3841905
• More on the bipartite decomposition of random graphs
• Covering a graph by complete bipartite graphs
• On the decomposition of random hypergraphs

zbMATH Keywords

decompositionrandom graphsbipartition number

Mathematics Subject Classification ID

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

Cites Work

• Reducibility among combinatorial problems
• On the Addressing Problem for Loop Switching
• Some remarks on the theory of graphs
• A simple proof of Graham and Pollak's theorem
• Weighted sums of certain dependent random variables
• A note on an inequality involving the normal distribution
• On colouring random graphs
• On the decomposition ofkn into complete bipartite graphs
• A polynomial space proof of the Graham-Pollak theorem
• A new proof of a theorem of Graham and Pollak
• Bipartite decomposition of random graphs
• A counting proof of the Graham-Pollak theorem
• More on the bipartite decomposition of random graphs
• Eigensharp Graphs: Decomposition into Complete Bipartite Subgraphs

Cited In (14)

• Addressing graph products and distance-regular graphs
• On the decomposition of random hypergraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the decomposition of graphs into complete bipartite graphs
• More on the bipartite decomposition of random graphs
• Bipartite decomposition of random graphs
• Decomposition of an infinite complete graph into complete bipartite subgraphs
• A critical probability for biclique partition of \(G_{n,p}\)
• On rainbow-cycle-forbidding edge colorings of finite graphs
• Probabilistic methods for decomposition dimension of graphs
• Title not available (Why is that?)
• Decomposing almost complete graphs by random trees
• Decomposition of product graphs into complete bipartite subgraphs

This page was built for publication: Decomposition of random graphs into complete bipartite graphs

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