Displaying similar documents to “The sizes of components in random circle graphs”

A note on domination parameters in random graphs

Anthony Bonato, Changping Wang (2008)

Discussiones Mathematicae Graph Theory

Similarity:

Domination parameters in random graphs G(n,p), where p is a fixed real number in (0,1), are investigated. We show that with probability tending to 1 as n → ∞, the total and independent domination numbers concentrate on the domination number of G(n,p).

Asymptotic properties of random graphs

Zbigniew Palka

Similarity:

CONTENTS1. Introduction...........................................................................5  1.1. Purpose and scope..........................................................5  1.2. Probability-theoretic preliminaries....................................6  1.3. Graphs............................................................................11  1.4. Random graphs..............................................................132. Vertex-degrees....................................................................15  2.1....

Infinite paths and cliques in random graphs

Alessandro Berarducci, Pietro Majer, Matteo Novaga (2012)

Fundamenta Mathematicae

Similarity:

We study the thresholds for the emergence of various properties in random subgraphs of (ℕ, <). In particular, we give sharp sufficient conditions for the existence of (finite or infinite) cliques and paths in a random subgraph. No specific assumption on the probability is made. The main tools are a topological version of Ramsey theory, exchangeability theory and elementary ergodic theory.

The Chromatic Number of Random Intersection Graphs

Katarzyna Rybarczyk (2017)

Discussiones Mathematicae Graph Theory

Similarity:

We study problems related to the chromatic number of a random intersection graph G (n,m, p). We introduce two new algorithms which colour G (n,m, p) with almost optimum number of colours with probability tending to 1 as n → ∞. Moreover we find a range of parameters for which the chromatic number of G (n,m, p) asymptotically equals its clique number.

Poisson convergence of numbers of vertices of a given degree in random graphs

Wojciech Kordecki (1996)

Discussiones Mathematicae Graph Theory

Similarity:

The asymptotic distributions of the number of vertices of a given degree in random graphs, where the probabilities of edges may not be the same, are given. Using the method of Poisson convergence, distributions in a general and particular cases (complete, almost regular and bipartite graphs) are obtained.

Random procedures for dominating sets in bipartite graphs

Sarah Artmann, Jochen Harant (2010)

Discussiones Mathematicae Graph Theory

Similarity:

Using multilinear functions and random procedures, new upper bounds on the domination number of a bipartite graph in terms of the cardinalities and the minimum degrees of the two colour classes are established.

Encores on cores.

Cain, Julie, Wormald, Nicholas (2006)

The Electronic Journal of Combinatorics [electronic only]

Similarity: