首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
Let M be a matroid. When M is 3-connected, Tutte's Wheels-and-Whirls Theorem proves that M has a 3-connected proper minor N with |E(M)−E(N)|=1 unless M is a wheel or a whirl. This paper establishes a corresponding result for internally 4-connected binary matroids. In particular, we prove that if M is such a matroid, then M has an internally 4-connected proper minor N with |E(M)−E(N)|?3 unless M or its dual is the cycle matroid of a planar or Möbius quartic ladder, or a 16-element variant of such a planar ladder.  相似文献   

2.
Tutte defined a k-separation of a matroid M to be a partition (A,B) of the ground set of M such that |A|,|B|k and r(A)+r(B)−r(M)<k. If, for all m<n, the matroid M has no m-separations, then M is n-connected. Earlier, Whitney showed that (A,B) is a 1-separation of M if and only if A is a union of 2-connected components of M. When M is 2-connected, Cunningham and Edmonds gave a tree decomposition of M that displays all of its 2-separations. When M is 3-connected, this paper describes a tree decomposition of M that displays, up to a certain natural equivalence, all non-trivial 3-separations of M.  相似文献   

3.
For a k-connected graph or matroid M, where k is a fixed positive integer, we say that a subset X of E(M) is k-removable provided M?X is k-connected. In this paper, we obtain a sharp condition on the size of a 3-connected binary matroid to have a 3-removable circuit.  相似文献   

4.
Let N be a minor of a 3-connected matroid M such that no proper 3-connected minor of M has N as a minor. This paper proves a bound on |E(M)−E(N)| that is sharp when N is connected.  相似文献   

5.
A standard matrix representation of a matroid M represents M relative to a fixed basis B, where contracting elements of B and deleting elements of E(M)–B correspond to removing rows and columns of the matrix, while retaining standard form. If M is 3-connected and N is a 3-connected minor of M, it is often desirable to perform such a removal while maintaining both 3-connectivity and the presence of an N-minor. We prove that, subject to a mild essential restriction, when M has no 4-element fans with a specific labelling relative to B, there are at least two distinct elements, s 1 and s 2, such that for each i ∈ {1, 2}, si(M/s i ) is 3-connected and has an N-minor when s i B, and co(M\s i ) is 3-connected and has an N-minor when s i E(M)–B. We also show that if M has precisely two such elements and P is the set of elements that, when removed in the appropriate way, retain the N-minor, then (P, E(M)–P) is a sequential 3-separation.  相似文献   

6.
This paper proves a preliminary step towards a splitter theorem for internally 4-connected binary matroids. In particular, we show that, provided M   or M?M? is not a cubic Möbius or planar ladder or a certain coextension thereof, an internally 4-connected binary matroid M with an internally 4-connected proper minor N   either has a proper internally 4-connected minor MM with an N  -minor such that |E(M)−E(M)|?3|E(M)E(M)|?3 or has, up to duality, a triangle T and an element e of T   such that M\eM\e has an N-minor and has the property that one side of every 3-separation is a fan with at most four elements.  相似文献   

7.
A matroid M is called minor-minimally 3-connected if M is 3-connected and, for each eE(M), either M?e or M/e is not 3-connected. In this paper, we prove a chain theorem for the class of minor-minimally 3-connected binary matroids. As a consequence, we obtain a chain theorem for the class of minor-minimally 3-connected graphs.  相似文献   

8.
An element e of a 3-connected matroid M is said to be superfluous provided M/e is 3-connected. In this paper, we show that a 3-connected matroid M with exactly k superfluous elements has at least
  相似文献   

9.
For a 3-connected binary matroid M, let dimA(M) be the dimension of the subspace of the cocycle space spanned by the non-separating cocircuits of M avoiding A, where AE(M). When A=∅, Bixby and Cunningham, in 1979, showed that dimA(M)=r(M). In 2004, when |A|=1, Lemos proved that dimA(M)=r(M)-1. In this paper, we characterize the 3-connected binary matroids having a pair of elements that meets every non-separating cocircuit. Using this result, we show that 2dimA(M)?r(M)-3, when M is regular and |A|=2. For |A|=3, we exhibit a family of cographic matroids with a 3-element set intersecting every non-separating cocircuit. We also construct the matroids that attains McNulty and Wu’s bound for the number of non-separating cocircuits of a simple and cosimple connected binary matroid.  相似文献   

10.
We investigate graphs G such that the line graph L(G) is hamiltonian connected if and only if L(G) is 3-connected, and prove that if each 3-edge-cut contains an edge lying in a short cycle of G, then L(G) has the above mentioned property. Our result extends Kriesell’s recent result in [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected line graph of a claw free graph is hamiltonian connected. Another application of our main result shows that if L(G) does not have an hourglass (a graph isomorphic to K5E(C4), where C4 is an cycle of length 4 in K5) as an induced subgraph, and if every 3-cut of L(G) is not independent, then L(G) is hamiltonian connected if and only if κ(L(G))≥3, which extends a recent result by Kriesell [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected hourglass free line graph is hamiltonian connected.  相似文献   

11.
We combine two well-known results by Mader and Thomassen, respectively. Namely, we prove that for any k-connected graph G (k≥4), there is an induced cycle C such that GV(C) is (k−3)-connected and GE(C) is (k−2)-connected. Both “(k−3)-connected” and “(k−2)-connected” are best possible in a sense.  相似文献   

12.
Let G be a 4-connected planar graph on n vertices. Malkevitch conjectured that if G contains a cycle of length 4, then G contains a cycle of length k for every k∈{n,n−1,…,3}. This conjecture is true for every k∈{n,n−1,…,n−6} with k≥3. In this paper, we prove that G also has a cycle of length n−7 provided n≥10.  相似文献   

13.
14.
For a graph G, a subset S of V(G) is called a shredder if GS consists of three or more components. We show that if G is a 5-connected graph with |V(G)|≥135, then the number of shredders of cardinality 5 of G is less than or equal to (2|V(G)|−10)/3.  相似文献   

15.
In an earlier paper with Whittle, we showed that there is a tree that displays, up to a natural equivalence, all non-trivial 3-separations of a 3-connected matroid M. The purpose of this paper is to give a polynomial-time algorithm for constructing such a tree for M.  相似文献   

16.
 Let N be a restriction of a 3-connected matroid M and let M be a 3-connected minor of M that is minimal having N as a restriction. This paper gives a best-possible upper bound on |E(M )−E(N)|. Received: July 17, 1998 Revised: March 15, 1999  相似文献   

17.
《Discrete Mathematics》2002,231(1-3):147-161
Lemos and Oxley proved that if M is a connected matroid with |E(M)|⩾3r(M), then M has a circuit C such that MC is connected. In this paper, we shall improve this result proving that for a simple and connected matroid M, if r(M)⩾7 and |E(M)|⩾3r(M)−3, then M has a circuit C such that MC is connected. To prove this result, we shall construct all the connected matroids having circumference at most five, with the exception of those which are 3-connected and have rank five.  相似文献   

18.
Connectivity of iterated line graphs   总被引:1,自引:0,他引:1  
Let k≥0 be an integer and Lk(G) be the kth iterated line graph of a graph G. Niepel and Knor proved that if G is a 4-connected graph, then κ(L2(G))≥4δ(G)−6. We show that the connectivity of G can be relaxed. In fact, we prove in this note that if G is an essentially 4-edge-connected and 3-connected graph, then κ(L2(G))≥4δ(G)−6. Similar bounds are obtained for essentially 4-edge-connected and 2-connected (1-connected) graphs.  相似文献   

19.
A nested orthogonal array is an OA(N,k,s,g) which contains an OA(M,k,r,g) as a subarray. Here r<s and M<N. Necessary conditions for the existence of such arrays are obtained in the form of upper bounds on k, given N, M, s, r and g. Examples are given to show that these bounds are quite powerful in proving nonexistence. The link with incomplete orthogonal arrays is also indicated.  相似文献   

20.
Let M=(E,F) be a rank-n matroid on a set E and B one of its bases. A closed set θE is saturated with respect to B, or B-saturated, when |θB|=r(θ), where r(θ) is the rank of θ.The collection of subsets I of E such that |Iθ|?r(θ), for every closed B-saturated set θ, turns out to be the family of independent sets of a new matroid on E, called base-matroid and denoted by MB. In this paper we prove some properties of MB, in particular that it satisfies the base-axiom of a matroid.Moreover, we determine a characterization of the matroids M which are isomorphic to MB for every base B of M.Finally, we prove that the poset of the closed B-saturated sets ordered by inclusion is isomorphic to the Boolean lattice Bn.  相似文献   

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

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