On two models of random graphs
| Autor: | Kurauskas, Valentas |
|---|---|
| Přispěvatelé: | MANSTAVIČIUS, EUGENIJUS, BAREIKIS, GINTAUTAS, BIKELIS, ALGIMANTAS JONAS, DUBICKAS, ARTŪRAS, JANUŠKEVIČIUS, ROMANAS, KRYLOVAS, ALEKSANDRAS, MAČIULIS, ALGIRDAS, Vilnius University |
| Jazyk: | litevština |
| Rok vydání: | 2013 |
| Předmět: |
Atsitiktiniai sankirtų grafai
Kurauskas random intersection graph minor-closed class algorithms Random intersection graph Minorinė grafų klasė Algoritmai Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Minor-closed class clique disjoint excluded minors Mathematics Algorithms |
| Popis: | The dissertation consists of two parts. In the first part several asymptotic properties of random intersection graphs are studied. They include birth thresholds for small complete subgraphs in the binomial random intersection graph, the clique number in sparse random intersection graphs and the chromatic index of random uniform hypergraphs. Several new methods and theoretically and practically relevant algorithms are proposed. Some results are illustrated with data from real-world networks. The second part deals with asymptotic enumeration and properties of graphs from minor-closed classes in the case when the excluded minors are disjoint. The class of graphs without k+1 (vertex-)disjoint cycles and more general classes of graphs without k+1 disjoint excluded minors (satisfying a condition related to fans) are considered. Typical graphs in such classes are shown to have a simple “k apex vertex” structure. Other asymptotic properties (connectivity, number of components, chromatic number, vertex degrees) are also determined. Finally, it is shown that typical graphs without k+1 disjoint minors K4 have a more complicated “2k+1 apex vertex” structure, and properties of such graphs are investigated. Part of the results is proved in greater generality. A variety of methods from computer science, graph theory, combinatorics and the theory of generating functions are applied. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|