Upper bounds on the non-3-colourability threshold of random graphs.
Fountoulakis, Nikolaos, McDiarmid, Colin (2002)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
Fountoulakis, Nikolaos, McDiarmid, Colin (2002)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
Zbigniew Palka (1981)
Colloquium Mathematicae
Similarity:
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).
Ramin Imany-Nabiyyi (2008)
Discussiones Mathematicae Graph Theory
Similarity:
We study random circle graphs which are generated by throwing n points (vertices) on the circle of unit circumference at random and joining them by an edge if the length of shorter arc between them is less than or equal to a given parameter d. We derive here some exact and asymptotic results on sizes (the numbers of vertices) of "typical" connected components for different ways of sampling them. By studying the joint distribution of the sizes of two components, we "go into" the structure...
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....
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.
Aiello, William, Chung, Fan, Lu, Linyuan (2001)
Experimental Mathematics
Similarity:
Liliana Alcón (2016)
Discussiones Mathematicae Graph Theory
Similarity:
We study domination between different types of walks connecting two non-adjacent vertices u and v of a graph (shortest paths, induced paths, paths, tolled walks). We succeeded in characterizing those graphs in which every uv-walk of one particular kind dominates every uv-walk of other specific kind. We thereby obtained new characterizations of standard graph classes like chordal, interval and superfragile graphs.
Ove Frank, Krzysztof Nowicki (1989)
Banach Center Publications
Similarity:
Emmanuel Breuillard, Ben J. Green, Robert Guralnick, Terence Tao (2015)
Journal of the European Mathematical Society
Similarity:
We show that random Cayley graphs of finite simple (or semisimple) groups of Lie type of fixed rank are expanders. The proofs are based on the Bourgain-Gamburd method and on the main result of our companion paper [BGGT].
H. D. O. F. Gronau, W. Just, W. Schade, Petra Scheffler, J. Wojciechowski (1987)
Applicationes Mathematicae
Similarity:
Beer, Elizabeth, Fill, James Allen, Janson, Svante, Scheinerman, Edward R. (2011)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
H. W. Berkowitz (1978)
Colloquium Mathematicae
Similarity:
Bretto, A. (1999)
Southwest Journal of Pure and Applied Mathematics [electronic only]
Similarity:
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.
Zdzisław Skupień (2007)
Discussiones Mathematicae Graph Theory
Similarity:
W. Wessel (1987)
Applicationes Mathematicae
Similarity: