Universality of Random Graphs for Graphs of Maximum Degree Two

DOI10.1137/130942437zbMATH Open1305.05209arXiv1310.5873OpenAlexW2073982255WikidataQ105584147 ScholiaQ105584147MaRDI QIDQ2935281FDOQ2935281

Authors: Jeong Han Kim, Sang June Lee 

Publication date: 22 December 2014

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

Abstract: For a family $mathcalF$ of graphs, a graph $G$ is called emph{$mathcalF$-universal} if $G$ contains every graph in $mathcalF$ as a subgraph. Let $mathcal{F}_n(d)$ be the family of all graphs on $n$ vertices with maximum degree at most $d$. Dellamonica, Kohayakawa, R"odl and Ruci'nski showed that, for $dgeq3$, the random graph $G(n,p)$ is $mathcal{F}_n(d)$-universal with high probability provided $$ for a sufficiently large constant $C=C(d)$. In this paper we prove the missing part of the result, that is, the random graph $G(n,p)$ is $mathcal{F}_n(2)$-universal with high probability provided $$ for a sufficiently large constant $C$.

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

Recommendations

• Universality of random graphs
• 2-universality in randomly perturbed graphs
• Optimal threshold for a random graph to be 2-universal
• Random graph processes with maximum degree 2
• The maximum degree of a random graph
• On universality of graphs with uniformly distributed edges
• Random graphs with a fixed maximum degree
• On universal representation of random graphs
• Universality for the distance in finite variance random graphs

zbMATH Keywords

graph embeddingrandom graphsuniversalitycontainment problembounded degree graphsuniversal graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cited In (13)

• Universality of random graphs
• Spanning structures and universality in sparse hypergraphs
• An improved upper bound on the density of universal random graphs
• On universal hypergraphs
• Spanning universality in random graphs
• Almost spanning universality in random graphs
• On a 2-parameter class of scale free random graphs
• Finding any given 2‐factor in sparse pseudorandom graphs efficiently
• Optimal threshold for a random graph to be 2-universal
• Universality of random graphs and rainbow embedding
• 2-universality in randomly perturbed graphs
• Almost-spanning universality in random graphs
• Sparse multipartite graphs as partition universal for graphs with bounded degree

This page was built for publication: Universality of Random Graphs for Graphs of Maximum Degree Two

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