Connectivity of the k-Out Hypercube

DOI10.1137/17M1134226MaRDI QIDQ4584954zbMATH OpenWikidataFDO

Authors Michael Anastos

Publication date 5 September 2018

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

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

zbMATH Keywords

\(k\)-out modelconnectivityhypercuberandom subgraphs

Mathematics Subject Classification ID

Connectivity (05C40) Random graphs (graph-theoretic aspects) (05C80)

Abstract: In this paper we study the connectivity properties of the random subgraph of the $n$-cube generated by the $k$-out model and denoted by $Q^n(k)$. Let $k$ be an integer, $1leqkleqn-1$. We let $Q^n(k)$ be the graph that is generated by independently including for every $vinV(Q^n)$ a set of $k$ distinct edges chosen uniformly from all the $$ sets of distinct edges that are incident to $v$. We study connectivity the properties of $Q^n(k)$ as $k$ varies. We show that w.h.p. $Q^n(1)$ does not contain a giant component i.e. a component that spans $Omega(2^n)$ vertices. Thereafter we show that such a component emerges when $k=2$. In addition the giant component spans all but $o(2^n)$ vertices and hence it is unique. We then establish the connectivity threshold found at $k_0=lo{g}_{2}n-2lo{g}_{2}lo{g}_{2}n$. The threshold is sharp in the sense that $Q^n(lfloor{k}_{0}floor)$ is disconnected but $Q^n(lceil{k}_{0}ceil+1)$ is connected w.h.p. Furthermore we show that w.h.p. $Q^n(k)$ is $k$-connected for every $kgeqlceil{k}_{0}ceil+1$.

Recommendations

• scientific article; zbMATH DE number 125454
• Component connectivity of the hypercubes
• Component connectivity of hypercubes
• Connectivity of matching graph of hypercube
• Extraconnectivity of hypercubes
• Structure connectivity of hypercubes
• Generalized connectivity of generalized hypercubes
• A Note on the Connectivity of m-Ary n-Dimensional Hypercubes
• The connectivity of exchanged hypercubes
• Neighbor connectivity of \(k\)-ary \(n\)-cubes

Cites work

• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Connectivity properties of random subgraphs of the cube
• Evolution of the n-cube
• Exact face-isoperimetric inequalities
• Expansion in ${\boldsymbol{n^{-1}}}$ for Percolation Critical Values on the $n$-cube and ${\boldsymbol{{\mathbb Z}^n}}$: the First Three Terms
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 3762003 (Why is no real title available?)
• scientific article; zbMATH DE number 3586242 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Hypercube percolation
• Introduction to Random Graphs
• Largest random component of a k-cube
• On random k-out subgraphs of large graphs
• On the connectivity of random m-orientable graphs and digraphs
• Random subgraphs of finite graphs. III: The phase transition for the n-cube
• The Evolution of Random Subgraphs of the Cube

Cited in

(1)

• A Note on the Connectivity of m-Ary n-Dimensional Hypercubes

This page was built for publication: Connectivity of the k-Out Hypercube

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