Original scientific paper

Two Models for Random Graphs with Bounded Degree

Krystyna T. Balińska ; Computer Science Center, The Technical University of Poznań, pl. M. Skłodowskiej-Curie 5, 60-965 Poznań, Poland
Michael L. Gargano ; Computer Science Department, Pace University, New York, NY 10038, USA
Louis V. Quintas ; Mathematics Department, Pace University, New York, NY 10038, USA

Abstract

Two digraphs both of whose nodes consist of the set of unlabeled graphs of order n having bounded vertex degree equal to f are studied. Adjacency in these digraphs is defined via one-edge transformations of the node graphs. Probabilities on the arcs are introduced so that one digraph is a strictly evolving absorbing Markov chain and the other an ergodic Markov chain. Probabilistic and deterministic results and problems concerning these Markov chains are presented. An example of physical interest in these chains is in models where the nodes of the digraphs are identified with Chemical species.

Keywords

random graph; Markov chain; bounded degree

Hrčak ID:

131803

URI

https://hrcak.srce.hr/131803

Publication date:

2.4.2001.

Visits: 530 *