On the Edge-Connectivity of an Uncertain Random Graph

Abstract

Connectivity is one of the most important concepts in graph theory. When graph theory is applied to complex systems with indeterminate factors, uncertainty and randomness are two basic types of indeterminacy. Therefore, the model of uncertain random graph was proposed via chance theory, in which some edges exist with degrees in probability measure and others exist with degrees in uncertain measure. This paper discusses the connectivity of an uncertain random graph with respect to edges. Concepts of k-connectivity index and edge-connectivity of an uncertain random graph are proposed. Methods and algorithms for calculating the k-connectivity index and the distribution of edge-connectivity are also proposed. In addition, some properties of them are discussed.

Keywords

• Chance theory
• connectivity index
• edge-connectivity
• graph theory
• uncertain random graph
• uncertainty theory