RANDOM GRAPHS WITH BOUNDED DEGREE

K.T. Balińska and L.V. Quintas, Random Graphs with Bounded Degree

Initiated in the 1980s, the study of random graphs with bounded degree has developed into an important branch of discrete mathematics as an intersection of graphs theory, combinatorics, and probability and has applications to chemistry, physics, biology, and computer science.

This is the first book that provides a comprehensive overview of this field. Based on the investigations carried out by the authors over a number of years, it contains a detailed description of probability models, the known results, and techniques used.

The fundamental model studied in this book is a random process for graphs with bounded degree. Graph-theoretical and probabilistic properties of its transition digraph with nodes corresponding to graphs with bounded degree are presented.

Among techniques used there are the classical tools of graph theory, a new method of solving asymptotic graph problems, and several exact and randomized combinatorial algorithms.

The unique strength of this book is how it can be used in a variety of ways so that it should be of interest to undergraduates, graduate students, and researchers. Specifically the book can be used as an introduction to graph theory smoothly leading into topics involving algorithmic computer science and random graph processes. These topics are then investigated at the intermediate level with many illustrative exercises and figures culminating with open problems at both the doctoral studies level and some suitable for advanced researchers.

Contents:

1. Introduction

2. Graphs and random graphs

3. Edge maximal f-graphs

4. The random f-graph process with f = 2

5. The random f-graph process with f ≥ 3

6. The order and size of D(n, f)

7. Maximum degrees in D(n, f)

8. Distance properties of U(n, f)

9. Hamilton paths in U(n, f)

10 Graph processes as Markov chains

11. The kinetic approach

12. The uniform model for edge maximal f-graphs

13. Applications

14. Solutions

Appendix: Tables and Figures. References. Index of definitions. Index of symbols.

Authors: Krystyna T. Balińska is a Professor of Computer Science at the Technical University of Poznań, Poland. Louis V. Quintas studied at Columbia University and then specializing in graph theory earned a Ph.D. in mathematics at the City University of New York. He is a Professor of Mathematics at Pace University, New York, U.S.A.

***

Badania w dziedzinie grafów losowych z ograniczonym stopniem wierzchołków należą do ważnego działu matematyki dyskretnej, łączącego teorię grafów i kombinatorykę z teorią prawdopodobieństwa i algorytmiką. Mają one zastosowania w rozwiązywaniu różnych zagadnień w chemii, fizyce, biologii, naukach społecznych i informatyce. Jest to pierwsza książka zawierająca wyczerpujący przegląd w tym zakresie, oparta na wynikach badań prowadzonych przez jej autorów od 20 lat. Przedstawiono w niej szczegółowy opis kilku modeli probabilistycznych, metod rozwiązywania problemów i uzyskanych wyników. Podstawowym modelem jest tu proces losowy o stanach odpowiadających grafom z ograniczonym stopniem. Przedstawiono właściwości probabilistyczne tego procesu i teoriografowe właściwości jego grafu przejść. Oprócz klasycznych metod teorii grafów wprowadzono ujęcie algorytmiczne rozwiązywanych problemów, zamieszczono wiele algorytmów kombinatorycznych zarówno dokładnych, jak i zrandomizowanych, opartych na próbkowaniu. Zaproponowano również nową metodę rozwiązywania problemów asymptotycznych w dziedzinie grafów z ograniczonym stopniem. Książka prowadzi czytelnika od elementarnych zagadnień teorii grafów i grafów losowych ilustrowanych licznymi przykładami i ćwiczeniami przez prezentację badań modeli grafów losowych z ograniczonym stopniem i ich zastosowań do sformułowania wielu problemów otwartych, których rozwiązanie wymaga znacznego zaawansowania w dziedzinie matematyki dyskretnej i informatyki. Cechą szczególną tych rozważań jest ich przydatność w nauczaniu projektowania algorytmów kombinatorycznych i rozwiązywania problemów optymalizacji dyskretnej na różnych kierunkach studiów: informatyka, automatyka i robotyka, elektronika i telekomunikacja. Modele grafów są tu wykorzystywane jako generatory klas grafów, z których metodą przesiewania wyodrębnia się zbiory struktur o wybranych właściwości.