首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 93 毫秒
1.
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.  相似文献   

2.
3.
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.  相似文献   

4.
图G的强边染色是指对图G进行正常边染色使得任意长度为3的路的三条边染不同的颜色.图G的强边色数,记为χ’s(G),是使得图G是强k边着色的最小正整数kk.2015年,Zang [arXiv:1510.00785]证明了:最大度△(G)=5的图G,χ’s(G)≤37.本文证明了:最大度△(G)=5且最大平均度小于8/3(或者14/5)的图G,χ’s(G)≤13 (或者14).另外,本文证明了:最大度△(G)≥3的不含K2,3-图子式的图G,χ’s(G)≤4△(G)-6,这个界是紧的.  相似文献   

5.
Based on our analysis of the hopcount of the shortest path between two arbitrary nodes in the class G p (N) of random graphs, the corresponding flooding time is investigated. The flooding time T N (p) is the minimum time needed to reach all other nodes from one node. We show that, after scaling, the flooding time T N (p) converges in distribution to the two-fold convolution (2*) of the Gumbel distribution function (z)=exp (–e z ), when the link density p N satisfies Np N /(log N)3 if N .  相似文献   

6.
本文证明了如下结果:设G是直径为4的简单囹,若G不含3阶完全子图K3,则G的Betti亏数ξ(G)≤2,因此有G的最大亏格γM(G)≥1/2β(G)-1.而且,在这种意义下,所得到的界是最好的.  相似文献   

7.
结合图的k-边形2-因子条件,确定了一类上可嵌入的3-连通图。  相似文献   

8.
9.
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 pc/nc 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.  相似文献   

10.
Let W n 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 W n has a discrete part. Moreover, the set of positive probability points is dense in (- +). In particular, the points , and 0 belong to this set.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号