共查询到20条相似文献,搜索用时 234 毫秒
1.
James Oxley Charles Semple Geoff Whittle 《Journal of Combinatorial Theory, Series B》2004,92(2):257-293
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. 相似文献
2.
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. 相似文献
3.
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? 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 M′ with an N -minor such that |E(M)−E(M′)|?3 or has, up to duality, a triangle T and an element e of T such that M\e has an N-minor and has the property that one side of every 3-separation is a fan with at most four elements. 相似文献
4.
5.
Carolyn Chun 《Journal of Combinatorial Theory, Series B》2011,101(3):141-189
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. 相似文献
6.
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. 相似文献
7.
David Barnette 《Israel Journal of Mathematics》1973,14(1):1-13
In this paper, we introduce three operations on planar graphs that we call face splitting, double face splitting, and subdivision
of hexagons. We show that the duals of the planar 4-connected graphs can be generated from the graph of the cube by these
three operations. That is, given any graphG that is the dual of a planar 4-connected graph, there is a sequence of duals of planar 4-connected graphsG
0,G
1, …,G
n such thatG
0 is the graph of the cube,G
n=G, and each graph is obtained from its predecessor by one of our three operations.
Research supported by a Sloan Foundation fellowship and by NSF Grant#GP-27963. 相似文献
8.
A.A. El-Atik H.M. Abu Donia A.S. Salama 《Journal of the Egyptian Mathematical Society》2013,21(1):63-67
In this paper, by using b-open (=γ-open) sets we study the concept of b-separated sets. With this concept we study the notion of b-connected sets and strongly b-connected sets. We give some properties of such concepts with some b-separation axioms and compact spaces. Finally, we construct a new topological space on a connected graph. 相似文献
9.
The prism graph is the dual of the complete graph on five vertices with an edge deleted, K 5\ e. In this paper we determine the class of binary matroids with no prism minor. The motivation for this problem is the 1963 result by Dirac where he identified the simple 3-connected graphs with no minor isomorphic to the prism graph. We prove that besides Dirac’s infinite families of graphs and four infinite families of non-regular matroids determined by Oxley, there are only three possibilities for a matroid in this class: it is isomorphic to the dual of the generalized parallel connection of F 7 with itself across a triangle with an element of the triangle deleted; it’s rank is bounded by 5; or it admits a non-minimal exact 3-separation induced by the 3-separation in P 9. Since the prism graph has rank 5, the class has to contain the binary projective geometries of rank 3 and 4, F 7 and PG(3, 2), respectively. We show that there is just one rank 5 extremal matroid in the class. It has 17 elements and is an extension of R 10, the unique splitter for regular matroids. As a corollary, we obtain Mayhew and Royle’s result identifying the binary internally 4-connected matroids with no prism minor Mayhew and Royle (Siam J Discrete Math 26:755–767, 2012). 相似文献
10.
Klaus Truemper 《Journal of Graph Theory》1987,11(4):531-536
Let K be a connected and undirected graph, and M be the polygon matroid of K. Assume that, for some k ? 1, the matroid M is k-separable and k-connected according to the matroid separability and connectivity definitions of W. T. Tutte. In this paper we classify the matroid k-separations of M in terms of subgraphs of K. 相似文献
11.
A matroid M is called minor-minimally 3-connected if M is 3-connected and, for each e∈E(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. 相似文献
12.
Peter J Slater 《Journal of Combinatorial Theory, Series B》1974,17(3):281-298
Having observed Tutte's classification of 3-connected graphs as those attainable from wheels by line addition and point splitting and Hedetniemi's classification of 2-connected graphs as those obtainable from K2 by line addition, subdivision and point addition, one hopes to find operations which classify n-connected graphs as those obtainable from, for example, Kn+1. In this paper I give several generalizations of the above operations and use Halin's theorem to obtain two variations of Tutte's theorem as well as a classification of 4-connected graphs. 相似文献
13.
An essential element of a 3-connected matroid M is one for which neither the deletion nor the contraction is 3-connected. Tutte's Wheels and Whirls Theorem proves that the only 3-connected matroids in which every element is essential are the wheels and whirls. In an earlier paper, the authors showed that a 3-connected matroid with at least one non-essential element has at least two such elements. This paper completely determines all 3-connected matroids with exactly two non-essential elements. Furthermore, it is proved that every 3-connected matroid M for which no single-element contraction is 3-connected can be constructed from a similar such matroid whose rank equals the rank in M of the set of elements e for which the deletion M\e is 3-connected. 相似文献
14.
It has previously been shown that if M is a maximum matching in a 3-connected graph G, other than K4, then M contains at least one contractible edge of G. In this paper, we give a constructive characterization of the 3-connected graphs G having a maximum matching containing only one contractible edge of G. 相似文献
15.
João Paulo Costalonga 《European Journal of Combinatorics》2012,33(1):72-81
Whittle proved, for k=1,2, that if N is a 3-connected minor of a 3-connected matroid M, satisfying r(M)−r(N)≥k, then there is a k-independent set I of M such that, for every x∈I, si(M/x) is a 3-connected matroid with an N-minor. In this paper, we establish this result for k=3. It is already known that it cannot be extended to greater values of k. But, here we also show that, in the graphic case, with the extra assumption that r(M)−r(N)≥6, we can guarantee the existence of a 4-independent set of M with such a property. Moreover, in the binary case, we show that if r(M)−r(N)≥5, then M has such a 4-independent set or M has a triangle T meeting 3 triads and such that M/T is a 3-connected matroid with an N-minor. 相似文献
16.
Nicholas C. Wormald 《Journal of Graph Theory》1985,9(4):563-573
The number of labeled cyclically 4-connected cubic graphs on n vertices is shown to satisfy a simple recurrence relation. The proof involves the unique decomposition of 3-connected cubic graphs into cyclically 4-connected components. 相似文献
17.
Eduardo Rivera-Campo 《Graphs and Combinatorics》1997,13(2):159-165
If M is a perfect matching in a k-connected graph G with independence number \(\alpha \le 1 + {3 \over 2}k\) , then M can be extended to a spanning tree of G with maximum degree at most three. 相似文献
18.
Raul Cordovil 《Discrete Mathematics》2009,309(4):655-665
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. 相似文献
19.
LetN andM be 3-connected matroids, whereN is a minor ofM on at least 4 elements, and lete be an element ofM and not ofN. Then, there exists a 3-connected minor \(\bar M\) ofM that usese, hasN as a minor, and has at most 4 elements more thanN. This result generalizes a theorem of Truemper and can be used to prove Seymour’s 2-roundedness theorem, as well as a result of Oxley on triples in nonbinary matroids. 相似文献
20.
Manoel Lemos 《Discrete Mathematics》2006,306(21):2790-2797
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