随机偏好连接图的中心极限定理

我们研究了一类具有随机顶点和边的随机连接图模型, 其中顶点的随机性由一个Poisson 点过程所决定, 边的随机性由一个概率连接函数所决定. 我们得到了带偏好的随机连接图模型的关于所有随机边的长度和的一个中心极限定理.     

Limit behaviors of random connected graphs driven by a Poisson process

We consider a class of random connected graphs with random vertices and random edges with the random distribution of vertices given by a Poisson point process with the intensity n localized at the vertices and the random distribution of the edges given by a connection function. Using the Avram-Bertsimas method constructed in 1992 for the central limit theorem on Euclidean functionals, we find the convergence rate of the central limit theorem process, the moderate deviation, and an upper bound for large deviations depending on the total length of all edges of the random connected graph.     

How many randomly colored edges make a randomly colored dense graph rainbow Hamiltonian or rainbow connected?

In this paper, we study the randomly edge colored graph that is obtained by adding randomly colored random edges to an arbitrary randomly edge colored dense graph. In particular, we ask how many colors and how many random edges are needed so that the resultant graph contains a fixed number of edge-disjoint rainbow-Hamilton cycles w.h.p. We also ask when, in the resultant graph, every pair of vertices is connected by a rainbow path w.h.p.     

The random planar graph process

We consider the following variant of the classical random graph process introduced by Erd?s and Rényi. Starting with an empty graph on n vertices, choose the next edge uniformly at random among all edges not yet considered, but only insert it if the graph remains planar. We show that for all ε > 0, with high probability, θ(n²) edges have to be tested before the number of edges in the graph reaches (1 + ε)n. At this point, the graph is connected with high probability and contains a linear number of induced copies of any fixed connected planar graph, the first property being in contrast and the second one in accordance with the uniform random planar graph model. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Vertex-Colored Encompassing Graphs

It is shown that every disconnected vertex-colored plane straight line graph with no isolated vertices can be augmented (by adding edges) into a connected plane straight line graph such that the new edges respect the coloring and the degree of every vertex increases by at most two. The upper bound for the increase of vertex degrees is best possible: there are input graphs that require the addition of two new edges incident to a vertex. The exclusion of isolated vertices is necessary: there are input graphs with isolated vertices that cannot be augmented to a connected vertex-colored plane straight line graph.     

The product representation of a locally dependent random graph

Directed graphs with random black and white colourings of edges such that the colours of edges from different vertices are mutually independent are called locally dependent random graphs. Two random graphs are equivalent if they cannot be distinguished from percolation processes on them if only the vertices are seen. A necessary and sufficient condition is given for when a locally dependent random graph is equivalent to a product random graph; that is one in which the edges can be grouped in such a way that within each group the colours of the edges are equivalent and between groups they are independent. As an application the random graph corresponding to a spatial general epidemic model is considered.     

On random perturbations of Hamiltonian systems with many degrees of freedom

We consider a class of random perturbations of Hamiltonian systems with many degrees of freedom. We assume that the perturbations consist of two components: a larger one which preserves the energy and destroys all other first integrals, and a smaller one which is a non-degenerate white noise type process. Under these assumptions, we show that the long time behavior of such a perturbed system is described by a diffusion process on a graph corresponding to the Hamiltonian of the system. The graph is homeomorphic to the set of all connected components of the level sets of the Hamiltonian. We calculate the differential operators which govern the process inside the edges of the graph and the gluing conditions at the vertices.     

Bounds on the eigenvalues of graphs with cut vertices or edges

In this paper, we characterize the extremal graph having the maximal Laplacian spectral radius among the connected bipartite graphs with n vertices and k cut vertices, and describe the extremal graph having the minimal least eigenvalue of the adjacency matrices of all the connected graphs with n vertices and k cut edges. We also present lower bounds on the least eigenvalue in terms of the number of cut vertices or cut edges and upper bounds on the Laplacian spectral radius in terms of the number of cut vertices.     

Some large deviation results for sparse random graphs

Summary. We obtain a large deviation principle (LDP) for the relative size of the largest connected component in a random graph with small edge probability. The rate function, which is not convex in general, is determined explicitly using a new technique. The proof yields an asymptotic formula for the probability that the random graph is connected. We also present an LDP and related result for the number of isolated vertices. Here we make use of a simple but apparently unknown characterisation, which is obtained by embedding the random graph in a random directed graph. The results demonstrate that, at this scaling, the properties `connected' and `contains no isolated vertices' are not asymptotically equivalent. (At the threshold probability they are asymptotically equivalent.) Received: 14 November 1996 / In revised form: 15 August 1997     

On k-leaf connectivity of a random graph

We prove that, in a random graph with n vertices and N = cn log n edges, the subgraph generated by a set of all vertices of degree at least k + 1 is k-leaf connected for c > 1/4. A threshold function for k-leaf connectivity is also found.     

A random environment for linearly edge-reinforced random walks on infinite graphs

We consider linearly edge-reinforced random walk on an arbitrary locally finite connected graph. It is shown that the process has the same distribution as a mixture of reversible Markov chains, determined by time-independent strictly positive weights on the edges. Furthermore, we prove bounds for the random weights, uniform, among others, in the size of the graph.      

Connected graphs without long paths

We determine the maximum number of edges in a connected graph with n vertices if it contains no path with k+1 vertices. We also determine the extremal graphs.     

Highway games on weakly cyclic graphs

A highway problem is determined by a connected graph which provides all potential entry and exit vertices and all possible edges that can be constructed between vertices, a cost function on the edges of the graph and a set of players, each in need of constructing a connection between a specific entry and exit vertex. Mosquera (2007) introduce highway problems and the corresponding cooperative cost games called highway games to address the problem of fair allocation of the construction costs in case the underlying graph is a tree. In this paper, we study the concavity and the balancedness of highway games on weakly cyclic graphs. A graph G is called highway-game concave if for each highway problem in which G is the underlying graph the corresponding highway game is concave. We show that a graph is highway-game concave if and only if it is weakly triangular. Moreover, we prove that highway games on weakly cyclic graphs are balanced.     

On the edge-density of 4-critical graphs

Gallai conjectured that every 4-critical graph on n vertices has at least 5/3n-2/3 edges. We prove this conjecture for 4-critical graphs in which the subgraph induced by vertices of degree 3 is connected.     

电阻-距离谱的若干结果

对连通图$G$的顶点$u$和$v$, $u$与$v$在$G$中的电阻距离$r_G(u,v)$等于相邻顶点之间的电阻为单位电阻的$G$对应的电网中$u$与$v$之间的等效电阻. 图$G$的电阻-距离特征值是$G$的电阻-距离矩阵$R(G)=(r_G(u,v))_{u,v\in V(G)}$的特征值. 我们分别确定了不同于完全图与完全图删去一条边后得到的图及给定割边数目的使得最大电阻-距离特征值取得最小值的唯一的连通图, 还讨论了最小电阻-距离特征值的性质.     

Novel method of identifying time series based on network graphs

In this article, we propose a novel method for transforming a time series into a complex network graph. The proposed algorithm is based on the spatial distribution of a time series. The characteristics of geometric parameters of a network represent the dynamic characteristics of a time series. Our algorithm transforms, respectively, a constant series into a fully connected graph, periodic time series into a regular graph, linear divergent time series into a tree, and chaotic time series into an approximately power law distribution network graph. We find that when the dimension of reconstructed phase space increases, the corresponding graph for a random time series quickly turns into a completely unconnected graph, while that for a chaotic time series maintains a certain level of connectivity. The characteristics of the generated network, including the total edges, the degree distribution, and the clustering coefficient, reflect the characteristics of the time series, including diverging speed, level of certainty, and level of randomness. This observation allows a chaotic time series to be easily identified from a random time series. The method may be useful for analysis of complex nonlinear systems such as chaos and random systems, by perceiving the differences in the outcomes of the systems—the time series—in the identification of the systemic levels of certainty or randomness. © 2011 Wiley Periodicals, Inc. Complexity, 2011     

On the power sequence of a graph

Necessary and sufficient conditions for a sequence (p ₁,p ₂, …,p _n ) of positive integers to be the power sequence of a connected graph onn vertices withm edges are given. The maximum power of a connected graph onn vertices withm edges and the class of all extremal graphs are also determined.     

Connectivity threshold of Bluetooth graphs

We study the connectivity properties of random Bluetooth graphs that model certain “ad hoc” wireless networks. The graphs are obtained as “irrigation subgraphs” of the well‐known random geometric graph model. There are two parameters that control the model: the radius r that determines the “visible neighbors” of each vertex and the number of edges c that each vertex is allowed to send to these. The randomness comes from the underlying distribution of vertices in space and from the choices of each vertex. We prove that no connectivity can take place with high probability for a range of parameters r, c and completely characterize the connectivity threshold (in c) for values of r close the critical value for connectivity in the underlying random geometric graph.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 45–66, 2014     

Randomness friendly graphs

We consider the two problems from extremal graph theory: 1. Given integer N, real p ϵ (0, 1) and a graph G, what is the minimum number of copies of G a graph H with N vertices and pN²/2 edges can contain? 2. Given an integer N and a graph G, what is the minimum number of copies of G an N-vertex graph H and its complement H¯ can contain altogether? In each of the problems, we say that G is “randomness friendly” if the number of its copies is nearly minimal when H is the random graph. We investigate how the two classes of graphs are related: the graphs which are “randomness friendly” in Problem 1 and those of Problem 2. In the latter problem, we discover new families of graphs which are “randomness friendly.” © 1996 John Wiley & Sons, Inc.