排序方式: 共有14条查询结果,搜索用时 31 毫秒
1.
John Ginsburg 《Order》1989,6(2):137-157
For a partially ordered setP and an elementx ofP, a subsetS ofP is called a cutset forx inP if every element ofS is noncomparable tox and every maximal chain ofP meets {x}∪S. We letc(P) denote the smallest integerk such that every elementx ofP has a cutsetS with ‖S‖?k: Ifc(P)?n we say thatP has then-cutset property. Our results bear on the following question: givenP, what is the smallestn such thatP can be embedded in a partially ordered set having then-cutset property? As usual, 2 n denotes the Boolean lattice of all subsets of ann-element set, andB n denotes the set of atoms and co-atoms of 2 n . We establish the following results: (i) a characterization, by means of forbidden configurations, of whichP can be embedded in a partially ordered set having the 1-cutset property; (ii) ifP contains a copy of 2 n , thenc(P)?2[n/2]?1; (iii) for everyn>3 there is a partially ordered setP containing 2 n such thatc(P)<c(2 n ); (iv) for every positive integern there is a positive integerN such that, ifB m is contained in a partially ordered set having then-cutset property, thenm?N. 相似文献
2.
On stable cutsets in claw-free graphs and planar graphs 总被引:4,自引:0,他引:4
A stable cutset in a connected graph is a stable set whose deletion disconnects the graph. Let and (claw) denote the complete (bipartite) graph on 4 and vertices. It is NP-complete to decide whether a line graph (hence a claw-free graph) with maximum degree five or a -free graph admits a stable cutset. Here we describe algorithms deciding in polynomial time whether a claw-free graph with maximum degree at most four or whether a (claw, )-free graph admits a stable cutset. As a by-product we obtain that the stable cutset problem is polynomially solvable for claw-free planar graphs, and also for planar line graphs.Thus, the computational complexity of the stable cutset problem is completely determined for claw-free graphs with respect to degree constraint, and for claw-free planar graphs. Moreover, we prove that the stable cutset problem remains NP-complete for -free planar graphs with maximum degree five. 相似文献
3.
Let Ln(q) denote the lattice of subspaces of ann-dimensional vector space over the finite field of q elements, ordered byinclusion. In this note, we prove that for all n and m the minimum cutsetfor an element A with
is justL(A) if m < n/ 2, is U(A) if m > n/ 2, and both L(A) andU(A) if m = n/ 2, where L(A) is the collection of all
such that
and
, and U(A) the collection of all
such that
and
. Hence a finite vector space analog isgiven for the theorem of Griggs and Kleitman that determines all the minimumcutsets for an element of a Boolean algebra. 相似文献
4.
5.
In this paper we prove that an atomistic lattice L of finite length is geometric if it has the nontrivial modular cutset condition, that is, every maximal chain of L contains a modular element which is different from the minimum element and the maximum element of L.
The first author is partially supported by the National Natural Science Foundation of China (Grant no. 10471016). 相似文献
6.
This paper proves that a geometric lattice of rank n is a modular lattice if its every maximal chain contains a modular element of rank greater than 1 and less than n. This result is generalized to a more general lattices of finite rank.
The first author is partially supported by the National Natural Science Foundation of China (Grant No. 10471016). 相似文献
7.
利用极小割集数算法计算网络系统可靠度 总被引:1,自引:0,他引:1
范莹蔷 《应用数学与计算数学学报》2003,17(1):63-66
本文利用极小割集数算法及Provan和Boll给出的两个定理计算了几个重要的R4(G)问题. 相似文献
8.
Let 2
[n] denote the poset of all subsets of [n]={1,2,...,n} ordered by inclusion. Following Gutterman and Shahriari (Order 14, 1998, 321–325) we consider a game G
n
(a,b,c). This is a game for two players. First, Player I constructs a independent maximal chains in 2
[n]. Player II will extend the collection to a+b independent maximal chains by finding another b independent maximal chains in 2
[n]. Finally, Player I will attempt to extend the collection further to a+b+c such chains. The last Player who is able to complete her move wins. In this paper, we complete the analysis of G
n
(a,b,c) by considering its most difficult instance: when c=2 and a+b+2=n. We prove, the rather surprising result, that, for n7, Player I wins G
n
(a,n–a–2,2) if and only if a3. As a consequence we get results about extending collections of independent maximal chains, and about cutsets (collections of subsets that intersect every maximal chain) of minimum possible width (the size of largest anti-chain). 相似文献
9.
Michele Conforti Grard Cornujols Ajai Kapoor Kristina Vukovi 《Journal of Graph Theory》2002,39(1):6-49
We prove a decomposition theorem for even‐hole‐free graphs. The decompositions used are 2‐joins and star, double‐star and triple‐star cutsets. This theorem is used in the second part of this paper to obtain a polytime recognition algorithm for even‐hole‐free graphs. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 6–49, 2002 相似文献
10.
A graph G is bridged if every cycle C of length at least 4 has vertices x,y such that dG(x,y) < dC(x,y). A cycle C is isometric if dG(x,y) = dC(x,y) for all x,y ∈ V(C). We show that every graph contractible to a graph with girth g has an isometric cycle of length at least g. We use this to show that every minimal cutset S in a bridged graph G induces a connected subgraph. We introduce a “crowning” construction to enlarge bridged graphs. We use this to construct examples showing that for every connected simple graph H with girth at least 6 (including trees), there exists a bridged graph G such that G has a unique minimum cutset S and that G[S] = H. This provides counterexamples to Hahn's conjecture that dG(u,v) ≤ 2 when u and v lie in a minimum cutset in a bridged graph G. We also study the convexity of cutsets in bridged graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 161–170, 2003 相似文献