✦ LIBER ✦

Random Induced Subgraphs of Generalizedn-Cubes

✍ Scribed by Christian M. Reidys

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 312 KB
Volume: 19
Category: Article
ISSN: 0196-8858
DOI: 10.1006/aama.1997.0553

No coin nor oath required. For personal study only.

✦ Synopsis

vertices are adjacent if they differ in exactly one coordinate. Random induced subgraphs,

. with probability . The first theorem shows that for s c ln n rn there exists n n a unique largest component in ⌫ -Q Q n which contains almost all vertices and that n ␣ Ž . the size of the second largest component is F Cnrln n , C ) 0. The second theorem describes connectivity and paths of ⌫ for constant probability ) 0. It is n proved that two vertices P, Q contained in the largest component of ⌫ , that have n distance k in Q Q , have a distance F k q k in ⌫ and are typically connected by a ␣ n large number of independent ⌫ -paths. Further, for any two vertices P, Q conn tained in the largest ⌫ component there exists a constant c ) 0 such that their n P , Q distance is F c n. ᮊ 1997 Academic Press P , Q Contents. 1. Introduction. 1.1. Notation. 1.2. Main results. 1.3. Proof of Theorem 1. 1.4. Proof of Theorem 2. References

📜 SIMILAR VOLUMES

Asymptotic Normality of the Vertex Degre

Asymptotic Normality of the Vertex Degree in Random Subgraphs of the n-Cube

✍ Urszula Konieczna 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 245 KB

We consider two types of random subgraphs of the n-cube. For these models we study the asymptotic behaviour of the number of vertices of degree d.

Distance-regular Isometric Subgraphs of

Distance-regular Isometric Subgraphs of the Halved Cubes

✍ S.V. Shpectorov 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 258 KB

We classify distance-regular graphs that are isometrically embeddable into halved cube graphs.

Pancyclic subgraphs of random graphs

✍ Choongbum Lee; Wojciech Samotij 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB

## Abstract An __n__‐vertex graph is called pancyclic if it contains a cycle of length __t__ for all 3≤__t__≤__n__. In this article, we study pancyclicity of random graphs in the context of resilience, and prove that if __p__>__n__^−1/2^, then the random graph __G__(__n, p__) a.a.s. satisfies the f

Random Subgraphs of Cayley Graphs overp-

Random Subgraphs of Cayley Graphs overp-Groups

✍ C.M. Reidys 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 146 KB

The subject of this paper is the size of the largest component in random subgraphs of Cayley graphs, X n , taken over a class of p-groups, G n . G n consists of p-groups, G n , with the following properties: , where K is some positive constant. We consider Cayley graphs X n = (G n , S n ), where S

Induced subgraphs of prescribed size

✍ Noga Alon; Michael Krivelevich; Benny Sudakov 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract A subgraph of a graph __G__ is called __trivial__ if it is either a clique or an independent set. Let __q(G)__ denote the maximum number of vertices in a trivial subgraph of __G__. Motivated by an open problem of Erdős and McKay we show that every graph __G__ on __n__ vertices for which

On induced subgraphs of a block

✍ Ladislav Nebeský 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 271 KB

If G is a block, then a vertex u of G is called critical if Gu is not a block. In this article, relationships between the localization of critical vertices and the localization of vertices of relatively small degrees (especially, of degree two) are studied. A block is called semicritical if a) each