排序方式: 共有3条查询结果,搜索用时 0 毫秒
1
1.
The (all-terminal) reliability of a graph G is the probability that all vertices are in the same connected component, given that vertices are always operational but edges fail independently each with probability p. Computing reliability is #P-complete, and hence is expected to be intractable. Consequently techniques for efficiently (and effectively) bounding reliability have been the major thrust of research in the area. We utilize a deep connection between reliability and chip firings on graphs to improve previous bounds for reliability. 相似文献
2.
Jason Bell 《Discrete Mathematics》2007,307(6):668-682
We show that each polynomial a(z)=1+a1z+?+adzd in N[z] having only real zeros is the f-polynomial of a multicomplex. It follows that a(z) is also the h-polynomial of a Cohen-Macaulay ring and is the g-polynomial of a simplicial polytope. We conjecture that a(z) is also the f-polynomial of a simplicial complex and show that the multicomplex result implies this in the special case that the zeros of a(z) belong to the real interval [-1,0). We also show that for fixed d the conjecture can fail for at most finitely many polynomials having the required form. 相似文献
3.
Yusuf Civan 《Journal of Combinatorial Theory, Series A》2007,114(7):1315-1331
A vertex coloring of a simplicial complex Δ is called a linear coloring if it satisfies the property that for every pair of facets (F1,F2) of Δ, there exists no pair of vertices (v1,v2) with the same color such that v1∈F1?F2 and v2∈F2?F1. The linear chromatic numberlchr(Δ) of Δ is defined as the minimum integer k such that Δ has a linear coloring with k colors. We show that if Δ is a simplicial complex with lchr(Δ)=k, then it has a subcomplex Δ′ with k vertices such that Δ is simple homotopy equivalent to Δ′. As a corollary, we obtain that lchr(Δ)?Homdim(Δ)+2. We also show in the case of linearly colored simplicial complexes, the usual assignment of a simplicial complex to a multicomplex has an inverse. Finally, we show that the chromatic number of a simple graph is bounded from above by the linear chromatic number of its neighborhood complex. 相似文献
1