共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
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. 相似文献
3.
4.
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. 相似文献
5.
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. 相似文献
6.
7.
8.
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
9.
《Discrete Mathematics》2022,345(1):112638
The beta invariant is related to the Chromatic and Tutte Polynomials and has been studied by Crapo [4], Brylawski [2], Oxley [7] and others. Crapo [4] showed that a matroid with at least two elements is connected if and only if its beta invariant is greater than zero. Brylawski [2] showed that a connected matroid has beta invariant one if and only if M is isomorphic to a serial-parallel network. Oxley [7] characterized all matroids with beta invariant two, three and four. In this paper, we first give a best possible lower bound on the beta invariant of 3-connected matroids, then we characterize all 3-connected matroids attaining the lower bound. We also characterize all binary matroids with beta invariant 5, 6, and 7. 相似文献
10.
Sanjay Rajpal 《Discrete Mathematics》1998,190(1-3):191-200
A matroid M of rank r k is k-paving if all of its circuits have cardinality exceeding r − k. In this paper, we develop some basic results concerning k-paving matroids and their connections with codes. Also, we determine all binary 2-paving matroids. 相似文献
11.
Trevor J. Gionet Jr. Erika L.C. King Yixiao Sha 《Discrete Applied Mathematics》2011,159(12):1225-1230
In 1995, Plummer (1992) [6] published a paper in which he gave a characterization of 4-regular, 4-connected, claw-free graphs. Based on that work, Hartnell and Plummer (1996) [5] published a paper on 4-connected, claw-free, well-covered graphs a year later. However, in his 1995 paper, Plummer inadvertently omitted some of the graphs with odd order. In this paper, we will complete Plummer’s characterization of all 4-connected, 4-regular, claw-free graphs, and then show the implications this has on the well-covered graphs he and Hartnell determined. In addition, we will characterize 4-connected, 4-regular, claw-free, well-dominated graphs. 相似文献
12.
A t-spanner of an undirected, unweighted graph G is a spanning subgraph
of G with the added property that for every pair of vertices in G, the distance between them in
is at most t times the distance between them in G. We are interested in finding a sparsest t-spanner, i.e., a t-spanner with the minimum number of edges. In the general setting, this problem is known to be NP-hard for all t2. For t5, the problem remains NP-hard for planar graphs, whereas for t{2,3,4}, the complexity of this problem on planar graphs is still unknown. In this paper we present a polynomial time approximation scheme for the problem of finding a sparsest 2-spanner of a 4-connected planar triangulation. 相似文献
13.
14.
15.
Let G be a 4-connected graph, and let Ec(G) denote the set of 4-contractible edges of G and let denote the set of those edges of G which are not contained in a triangle. Under this notation, we show that if , then we have . 相似文献
16.
A unique factorization theorem for matroids 总被引:2,自引:0,他引:2
We study the combinatorial, algebraic and geometric properties of the free product operation on matroids. After giving cryptomorphic definitions of free product in terms of independent sets, bases, circuits, closure, flats and rank function, we show that free product, which is a noncommutative operation, is associative and respects matroid duality. The free product of matroids M and N is maximal with respect to the weak order among matroids having M as a submatroid, with complementary contraction equal to N. Any minor of the free product of M and N is a free product of a repeated truncation of the corresponding minor of M with a repeated Higgs lift of the corresponding minor of N. We characterize, in terms of their cyclic flats, matroids that are irreducible with respect to free product, and prove that the factorization of a matroid into a free product of irreducibles is unique up to isomorphism. We use these results to determine, for K a field of characteristic zero, the structure of the minor coalgebra of a family of matroids that is closed under formation of minors and free products: namely, is cofree, cogenerated by the set of irreducible matroids belonging to . 相似文献
17.
18.
Frédéric Meunier 《Journal of Combinatorial Theory, Series A》2008,115(2):317-325
In 1989, Robert W. Freund published an article about generalizations of the Sperner lemma for triangulations of n-dimensional polytopes, when the vertices of the triangulations are labeled with points of Rn. For y∈Rn, the generalizations ensure, under various conditions, that there is at least one simplex containing y in the convex hull of its labels. Moreover, if y is generic, there is generally a parity assertion, which states that there is actually an odd number of such simplices.For one of these generalizations, contrary to the others, neither a combinatorial proof, nor the parity assertion were established. Freund asked whether a corresponding parity assertion could be true and proved combinatorially.The aim of this paper is to give a positive answer, using a technique which can be applied successfully to prove several results of this type in a very simple way. We prove actually a more general version of this theorem. This more general version was published by van der Laan, Talman and Yang in 2001, who proved it in a non-combinatorial way, without the parity assertion. 相似文献
19.
Daniel J. Miller 《Transactions of the American Mathematical Society》2006,358(10):4395-4439
It is shown that Lion and Rolin's preparation theorem for globally subanalytic functions holds for the collection of definable functions in any expansion of the real ordered field by a Weierstrass system.
20.
Wei Li Yao 《数学学报(英文版)》2013,29(10):1997-2012
Let fk(n) be the characteristic function of n with Ω(n) = k,and Tk(x,α) =∑n≤xfk(n)e(nα).The main purpose of this paper is to establish a Bombieri-type mean-value theorem for Tk(x,α),via using the modified Huxley-Hooley contour and the large-sieve type zero-density estimate for Dirichlet L-functions.The result plays an important role in handling the enlarge major arcs when we try to solve the Waring-Goldbach type problem by the circle method. 相似文献