Temat: random graph - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Chvátals Condition cannot hold for both a graph and its complement
Autorzy:: Kostochka, Alexandr
West, Douglas
Powiązania:: https://bibliotekanauki.pl/articles/743881.pdf
Data publikacji:: 2006
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: Hamiltonian cycle
Chvátal's Condition
random graph
Opis:: Chvátal's Condition is a sufficient condition for a spanning cycle in an n-vertex graph. The condition is that when the vertex degrees are d₁, ...,dₙ in nondecreasing order, i < n/2 implies that $d_i > i$ or $d_{n-i} ≥ n-i$. We prove that this condition cannot hold in both a graph and its complement, and we raise the problem of finding its asymptotic probability in the random graph with edge probability 1/2.
Źródło:: Discussiones Mathematicae Graph Theory; 2006, 26, 1; 73-76
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: Ramsey Properties of Random Graphs and Folkman Numbers
Autorzy:: Rödl, Vojtěch
Ruciński, Andrzej
Schacht, Mathias
Powiązania:: https://bibliotekanauki.pl/articles/31341650.pdf
Data publikacji:: 2017-08-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: Ramsey property
random graph
Folkman number
Opis:: For two graphs, G and F, and an integer r ≥ 2 we write G → (F)_r if every r-coloring of the edges of G results in a monochromatic copy of F. In 1995, the first two authors established a threshold edge probability for the Ramsey property G(n, p) → (F)_r, where G(n, p) is a random graph obtained by including each edge of the complete graph on n vertices, independently, with probability p. The original proof was based on the regularity lemma of Szemerédi and this led to tower-type dependencies between the involved parameters. Here, for r = 2, we provide a self-contained proof of a quantitative version of the Ramsey threshold theorem with only double exponential dependencies between the constants. As a corollary we obtain a double exponential upper bound on the 2-color Folkman numbers. By a different proof technique, a similar result was obtained independently by Conlon and Gowers.
Źródło:: Discussiones Mathematicae Graph Theory; 2017, 37, 3; 755-776
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Tytuł:: The independent domination number of a random graph
Autorzy:: Clark, Lane
Johnson, Darin
Powiązania:: https://bibliotekanauki.pl/articles/743841.pdf
Data publikacji:: 2011
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: random graph
two-point concentration
independent domination
Opis:: We prove a two-point concentration for the independent domination number of the random graph $G_{n,p}$ provided p²ln(n) ≥ 64ln((lnn)/p).
Źródło:: Discussiones Mathematicae Graph Theory; 2011, 31, 1; 129-142
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 4.

Tytuł:: Asymptotic Behavior of the Edge Metric Dimension of the Random Graph
Autorzy:: Zubrilina, Nina
Powiązania:: https://bibliotekanauki.pl/articles/32083896.pdf
Data publikacji:: 2021-05-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: random graph
edge dimension
Suen’s inequality
Opis:: Given a simple connected graph $G(V,E)$, the edge metric dimension, denoted $edim(G)$, is the least size of a set $S ⊆ V$ that distinguishes every pair of edges of $G$, in the sense that the edges have pairwise different tuples of distances to the vertices of $S$. In this paper we prove that the edge metric dimension of the Erdős-Rényi random graph $G(n, p)$ with constant $p$ is given by \[edim(G(n,p))=(1+o(1))\frac{4 \log n}{\log(1/q)},\] where $q = 1 − 2p(1 − p)^2(2 − p)$.
Źródło:: Discussiones Mathematicae Graph Theory; 2021, 41, 2; 589-599
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja