On handshakes in random graphs

In [Y. Métivier, N. Saheb, A. Zemmari, Analysis of a randomized rendezvous algorithm, Inform. and Comput. 184 (2003) 109-128], the authors introduce and analyze a randomized procedure to implement handshakes in graphs. In this paper, we investigate the same problem in random graphs. We prove results on the probability of success and we study the distribution of the random variable which counts the number of handshakes in the graph.     

Clustering in random line graphs

We investigate the degree distribution P(k) and the clustering coefficient C of the line graphs constructed on the Erdös-Rényi networks, the exponential and the scale-free growing networks. We show that the character of the degree distribution in these graphs remains Poissonian, exponential and power law, respectively, i.e. the same as in the original networks. When the mean degree 〈k〉 increases, the obtained clustering coefficient C tends to 0.50 for the transformed Erdös-Rényi networks, to 0.53 for the transformed exponential networks and to 0.61 for the transformed scale-free networks. These results are close to theoretical values, obtained with the model assumption that the degree-degree correlations in the initial networks are negligible.     

Undecidable statements and random graphs

In this paper we will consider random graphsG _n,p ,p=n ^– a rational number between 0 and 1. We show that there is no decision procedure that separates those first order statements that hold almost always inG _n,p from those whose negation holds almost always.     

Generating random connected planar graphs

Connected planar graphs are of interest to a variety of scholars. Being able to simulate a database of such graphs with selected properties would support specific types of inference for spatial analysis and other network-based disciplines. This paper presents a simple, efficient, and flexible connected planar graph generator for this purpose. It also summarizes a comparison between an empirical set of specimen graphs and their simulated counterpart set, and establishes evidence for positing a conjecture about the principal eigenvalue of connected planar graphs. Finally, it summarizes a probability assessment of the algorithm’s outcomes as well as a comparison between the new algorithm and selected existing planar graph generators.     

Large independent sets in random regular graphs

We present algorithmic lower bounds on the size _sd$s_d$ of the largest independent sets of vertices in random d$d$-regular graphs, for each fixed d≥3$d\ge 3$. For instance, for d=3$d=3$ we prove that, for graphs on n$n$ vertices, _sd≥0.43475n$s_d\ge 0.43475n$ with probability approaching one as n$n$ tends to infinity.     

Reconstruction of graphs based on random walks

The analysis of complex networks is of major interest in various fields of science. In many applications we face the challenge that the exact topology of a network is unknown but we are instead given information about distances within this network. The theoretical approaches to this problem have so far been focusing on the reconstruction of graphs from shortest path distance matrices. Often, however, movements in networks do not follow shortest paths but occur in a random fashion. In these cases an appropriate distance measure can be defined as the mean length of a random walk between two nodes — a quantity known as the mean first hitting time.In this contribution we investigate whether a graph can be reconstructed from its mean first hitting time matrix and put forward an algorithm for solving this problem. A heuristic method to reduce the computational effort is described and analyzed. In the case of trees we can even give an algorithm for reconstructing graphs from incomplete random walk distance matrices.     

Generating labeled planar graphs uniformly at random

We present a deterministic polynomial time algorithm to sample a labeled planar graph uniformly at random. Our approach uses recursive formulae for the exact number of labeled planar graphs with n$n$ vertices and m$m$ edges, based on a decomposition into 1-, 2-, and 3-connected components. We can then use known sampling algorithms and counting formulae for 3-connected planar graphs.     

判定大型图中可到达性的随机区间标记索引

提出一种基于随机区间标记理论的可到达判定的方法RIABG, 它可以有效地处理非常大型的图, 并且具有良好的可扩展性。RIABG具有线性的检索时间和空间复杂度, 查询时间可以是常数时间, 也可以根据图的大小而进行线性变化。真实数据集上的实验表明, RIABG可以有效处理大规模有向图的可达性判定问题。     

The distant-2 chromatic number of random proximity and random geometric graphs

We are interested in finding bounds for the distant-2 chromatic number of geometric graphs drawn from different models. We consider two undirected models of random graphs: random geometric graphs and random proximity graphs for which sharp connectivity thresholds have been shown. We are interested in a.a.s. connected graphs close just above the connectivity threshold. For such subfamilies of random graphs we show that the distant-2-chromatic number is Θ(logn) with high probability. The result on random geometric graphs is extended to the random sector graphs defined in [J. Díaz, J. Petit, M. Serna. A random graph model for optical networks of sensors, IEEE Transactions on Mobile Computing 2 (2003) 143-154].     

Kolmogorov random graphs only have trivial stable colorings

In this paper, we prove that random graphs only have trivial stable colorings. Our result improves Theorem 4.1 in [Proc. 20th IEEE Symp. on Foundations of Comput. Sci., 1979, pp. 39-46]. It can be viewed as an effective version of Corollary 2.13 in [SIAM J. Comput. 29 (2) (2000) 590-599]. As a byproduct, we also give an upper bound of the size of induced regular subgraphs in random graphs.     

Asymptotic formulas for connectivity probabilities of random graphs

Known asymptotic formulas are used to analyze the connectivity probability of graphs with highly reliable and poorly reliable edges. The conventional methods used to calculate the coefficients in these formulas require a number of arithmetic operations that grows geometrically with the growing number of graph edges. The adjacency matrix of the dual graph for highly reliable edges and the Kirchhoff matrix for poorly reliable edges result in algorithms of cubic complexity.     

Stochastic cooperative distributed grammar systems and random graphs

We introduce an alternative definition of random graphs as a language generated by a stochastic cooperating distributed grammar system. We show a relationship between our definition and four known definitions of random graphs, an example of using our model to prove graph-theoretic properties, and we define k-probabilistic model of random graphs as an extension. The first important acquisition of our definition is that only a small modification of a stochastic cooperating distributed grammar system may effect the substantial change of the generated random graph model. Other important result resides in the fact that our approach enables the use of a new proving technique in the random graph theory which is based on the generative paradigm inherent in the formal languages theory. Received: 14 May 2002 / 30 October 2002 RID="*" ID="*" Supported by the VEGA grant No. 1/7152/20.