✦ LIBER ✦

Kernels in random graphs

✍ Scribed by W.Fernandez de la Vega

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 214 KB
Volume: 82
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(90)90327-e

No coin nor oath required. For personal study only.

✦ Synopsis

For each fixed p, the random directed graph D(n, p) on n vertices with (directed) edge probability p possesses a kernel with probability tending to 1 as n + a.

Pour chaque p fixe, le graphe alCatoire D(n, p) a n sommets et probabilitts des arcs Cgales B p posstde un noyau avec une probabilit6 tendant vers 1 quand n+o3.

📜 SIMILAR VOLUMES

On kernels in strongly connected graphs

✍ M. Anciaux-Mundeleer; P. Hansen 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 204 KB

On kernels in i-triangulated graphs

✍ F Maffray 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 319 KB

A directed graph is said to be kernel-perfect if every induced subgraph possesses a kernel (independent, absorbing subset). A necessary condition for a graph to be kernel-perfect is that every complete subgraph C has an absorbing vertex (i.e., a successor of all vertices of C). In this work, we show

On the existence of kernels and h-kernel

On the existence of kernels and h-kernels in directed graphs

✍ H. Galeana-Sánchez 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 272 KB

Trees in random graphs

✍ P. Erdös; Z. Palka 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 183 KB

Cycles in random graphs

✍ Tomasz Łuczak 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 348 KB

tuczak, T., Cycles in random graphs, Discrete Mathematics 98 (1991) 231-236. Let G(n, p) be a graph on n vertices in which each possible edge is presented independently with probability p = p(n) and u'(n, p) denote the number of vertices of degree 1 in G(n, p). It is shown that if E > 0 and rip(n)))

Kernels in graphs with a clique-cutset

✍ Henry Jacob 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 138 KB

We consider graphs that have a clique-cutset, and we show that this property preserves the existence of a kernel in a certain sense. We consider finite directed graphs that do not have multiple arcs or loops, but there may be symmetric arcs between some pairs of vertices. Let G = (V, A) be a direct