Universality of Random Graphs for Graphs of Maximum Degree Two

DOI10.1137/130942437MaRDI QIDQ2935281zbMATH OpenOpenAlexWikidataFDO

Authors Jeong Han Kim, Sang June Lee

Publication date 22 December 2014

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

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

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)

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$.

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

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
• Universality of random graphs and rainbow embedding
• Optimal threshold for a random graph to be 2-universal
• Finding any given 2‐factor in sparse pseudorandom graphs efficiently
• 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)