We consider random graphs with edge probability βn?α, where n is the number of vertices of the graph, β > 0 is fixed, and α = 1 or α = (l + 1) /l for some fixed positive integer l. We prove that for every first-order sentence, the probability that the sentence is true for the random graph has an asymptotic limit. 相似文献
A routing R of a graph G is a set of n(n ? 1) elementary paths R(u, v) specified for all ordered pairs (u, v) of vertices of G. The vertex-forwarding index ξ(G) of G, is defined by Where ξ(G, R) is the maximum number of paths of the routing R passing through any vertex of G and the minimum is taken over all the routings of G. Let Gp denote the random graph on n vertices with edge probability p and let m = np. It is proved among other things that, under natural growth conditions on the function p = p(n), the ratio Tends to 1 in probability as n tends to infinity. 相似文献
Based on our analysis of the hopcount of the shortest path between two arbitrary nodes in the class Gp (N) of random graphs, the corresponding flooding time is investigated. The flooding time TN (p) is the minimum time needed to reach all other nodes from one node. We show that, after scaling, the flooding time TN (p) converges in distribution to the two-fold convolution (2*) of the Gumbel distribution function (z)=exp (–e–z), when the link density pN satisfies NpN/(log N)3 if N . 相似文献
A proper 2-tone k-coloring of a graph is a labeling of the vertices with elements from \({\binom{[k]}{2}}\) such that adjacent vertices receive disjoint labels and vertices distance 2 apart receive distinct labels. The 2-tone chromatic number of a graph G, denoted τ2(G) is the smallest k such that G admits a proper 2-tone k coloring. In this paper, we prove that w.h.p. for \({p\geq Cn^{-1/4} {\rm ln}^{9/4}n, \tau_2(G_{n, p}) = (2 + o(1))\chi(G_{n, p})}\) where \({\chi}\) represents the ordinary chromatic number. For sparse random graphs with p = c/n, c constant, we prove that \({\tau_2(G_{n, p}) = \lceil{({\sqrt{8\Delta + 1} + 5})/{2}}}\) where Δ represents the maximum degree. For the more general concept of t-tone coloring, we achieve similar results. 相似文献
Let Wn be an n × n random symmetric sparse matrix with independent identically distributed entries such that the values 1 and 0 are taken with probabilities p/n and 1-p/n, respectively; here
is independent of n. We show that the limit of the expected spectral distribution functions of Wn has a discrete part. Moreover, the set of positive probability points is dense in (- +). In particular, the points
, and 0 belong to this set. 相似文献