共查询到20条相似文献,搜索用时 0 毫秒
1.
Sean McGuinness 《Combinatorica》2005,25(4):439-450
Let G be a k-connected graph G having circumference c ≥ 2k. It is shown that for k ≥ 2, then there is a bond B which intersects every cycle of length c-k + 2 or greater. 相似文献
2.
Consider the class of matroids M with the property that M is not isomorphic to a wheel graph, but has an element e such that both M\e and M/e are isomorphic to a series-parallel extension of a wheel graph. We give a constructive characterization of such matroids by determining explicitly the 3-connected members of the class. We also relate this problem with excluded minor problems.Received May 30, 2003 相似文献
3.
Dillon Mayhew 《Graphs and Combinatorics》2006,22(3):383-389
A classical result of Dirac's shows that, for any two edges and any n−2 vertices in a simple n-connected graph, there is a cycle that contains both edges and all n−2 of the vertices. Oxley has asked whether, for any two elements and any n−2 cocircuits in an n-connected matroid, there is a circuit that contains both elements and that has a non-empty intersection with all n−2 of the cocircuits. By using Seymour's decomposition theorem and results of Oxley and Denley and Wu, we prove that a slightly
stronger property holds for regular matroids. 相似文献
4.
Let t(G) be the number of spanning trees of a connected graph G, and let b(G) be the number of bases of the bicircular matroid B(G). In this paper we obtain bounds relating b(G) and t(G), and study in detail the case where G is a complete graph Kn or a complete bipartite graph Kn,m.Received April 25, 2003 相似文献
5.
Graph Connectivity After Path
Removal 总被引:1,自引:0,他引:1
Let G be a graph and
u, v be two distinct vertices of
G. A u—v path P is called nonseparating if
G—V(P) is connected. The purpose of this
paper is to study the number of nonseparating
u—v path for two arbitrary
vertices u and
v of a given graph. For a
positive integer k, we will
show that there is a minimum integer (k) so that if G is an (k)-connected graph and
u and v are two arbitrary vertices in
G, then there exist
k vertex disjoint paths
P
1[u,v], P
2[u,v], . . ., P
k
[u,v], such that G—V (P
i
[u,v]) is connected for every
i (i = 1, 2, ..., k). In fact, we will prove that
(k) 22k+2. It is known that (1) = 3.. A
result of Tutte showed that (2) = 3. We show that (3) = 6. In
addition, we prove that if G
is a 5-connected graph, then for every pair of vertices
u and v there exists a path
P[u, v] such that G—V(P[u,
v]) is 2-connected.* Supported by NSF grant No.
DMS-0070059 Supported by ONR grant
N00014-97-1-0499 Supported by NSF grant No. 9531824 相似文献
6.
A polynomial, called the Penrose polynomial, is studied for binary matroids, generalizing previous work on plane graphs. In particular, several formulae of Penrose are extended via the theory of isotropic systems. (Received 9 February, 2000; in revised form 26 June 2000) 相似文献
7.
Andrew Thomason 《Combinatorica》1997,17(1):125-134
Arcane two-edge-colourings of complete graphs were described in [13], in which there are significantly fewer monochromaticK
r
's than in a random colouring (so disproving a conjecture of Erds [2]). Jagger, ovíek and Thomason [7] showed that the same colourings have fewer monochromaticG's than do random colourings for any graphG containingK
4.The purpose of this note is to point out that these colourings are not as obscure as might appear. There is in fact a large, natural and easily described class of colourings of the above kind; the specific examples used in [13] and [7] fall into this class. 相似文献
8.
Oliver Pretzel 《Order》1995,12(2):135-147
We prove generalizations to chain groups, of Minty's Arc Colouring Lemma and its extension, the well-known Farkas Lemma. In these the orientation of the edges is replaced by an arbitrary chain.A function on a chain groupN isrepresentable if there exists a chainR such that (X)=R·X for allXN. Anorientation is a chain with values ±1. We prove that for a regular chain group a linear function that is representable by an orientation for each chainXN locally, is representable by an orientation globally. 相似文献
9.
Cycles in weighted graphs 总被引:2,自引:0,他引:2
A weighted graph is one in which each edgee is assigned a nonnegative numberw(e), called the weight ofe. The weightw(G) of a weighted graphG is the sum of the weights of its edges. In this paper, we prove, as conjectured in [2], that every 2-edge-connected weighted graph onn vertices contains a cycle of weight at least 2w(G)/(n–1). Furthermore, we completely characterize the 2-edge-connected weighted graphs onn vertices that contain no cycle of weight more than 2w(G)/(n–1). This generalizes, to weighted graphs, a classical result of Erds and Gallai [4]. 相似文献
10.
A long-standing conjecture of Erd?s and Simonovits is that ex(n,C2k), the maximum number of edges in an n-vertex graph without a 2k-gon is asymptotically as n tends to infinity. This was known almost 40 years ago in the case of quadrilaterals. In this paper, we construct a counterexample to the conjecture in the case of hexagons. For infinitely many n, we prove that
11.
János Komlós 《Combinatorica》1997,17(3):393-400
We estimate the number of vertices/edges necessary to cover all odd cycles in graphs of given order and odd girth.To the memory of Pál Erds 相似文献
12.
Yahya Ould Hamidoune 《Combinatorica》1982,2(2):143-147
Behzad, Chartrand and Wall conjectured that the girth of a diregular graph of ordern and outdegreer is not greater than [n /r]. This conjecture has been proved forr=2 by Behzad and forr=3 by Bermond. We prove that a digraph of ordern and halfdegree ≧4 has girth not exceeding [n / 4]. We also obtain short proofs of the above results. Our method is an application of the theory of connectivity of digraphs. 相似文献
13.
In his thesis [3] M. J. Piff conjectured that a matroid, which is algebraic over a fieldFit) witht transcendent overF, must be algebraic overF. Two proofs have appeared, one by Shameeva [5] and another one by the author [2], but both are unsatisfactory. In this paper I will settle conjecture by applying a theorem of Seidenberg. 相似文献
14.
E. Győri 《Combinatorica》1989,9(1):101-102
Research partially supported bv Hungarian National Foundation for Scientific Research Grant no. 1812. 相似文献
15.
Mark Jerrum 《Combinatorica》2006,26(6):733-742
The property of balance (in the sense of Feder and Mihail) is investigated in the context of paving matroids. The following
examples are exhibited: (a) a class of “sparse” paving matroids that are balanced, but at the same time rich enough combinatorially
to permit the encoding of hard counting problems; and (b) a paving matroid that is not balanced. The computational significance
of (a) is the following. As a consequence of balance, there is an efficient algorithm for approximating the number of bases
of a sparse paving matroid within specified relative error. On the other hand, determining the number of bases exactly is
likely to be computationally intractable.
* The work described here was supported by the grant “Sharper analysis of randomised algorithms” from the UK Engineering and
Physical Sciences Research Council. 相似文献
16.
Wolfgang Mader 《Combinatorica》2005,25(4):425-438
We determine all graphs on n ≥ 3 vertices with 3n-6 edges which do not contain a subdivision of K5. These are exactly the graphs which one gets from any number of disjoint maximal planar graphs by successively pasting along
triangles. 相似文献
17.
Given a directed edge-weighted graph and k source-sink pairs, the Minimum Directed Multicut Problem is to find an edge subset with minimal weight, that separates each source-sink pair. Determining the minimum multicut in directed or undirected graphs is NP-hard. The fractional version of the minimum multicut problem is dual to the maximum multicommodity flow problem. The integrality gap for an instance of this problem is the ratio of the minimum weight multicut to the minimum weight fractional multicut; trivially this gap is always at least 1 and it is easy to show that it is at most k. In the analogous problem for undirected graphs this upper bound was improved to O(log k).In this paper, for each k an explicit family of examples is presented each with k source-sink pairs for which the integrality gap can be made arbitrarily close to k. This shows that for directed graphs, the trivial upper bound of k can not be improved.* This work was supported in part by NSF grant CCR-9700239 and by DIMACS. This work was done while a postdoctoral fellow at DIMACS. 相似文献
18.
Solving an old conjecture of Szele we show that the maximum number of directed Hamiltonian paths in a tournament onn vertices is at mostc · n
3/2
· n!/2
n–1, wherec is a positive constant independent ofn.Research supported in part by a U.S.A.-Israel BSF grant and by a Bergmann Memorial Grant. 相似文献
19.
A weighted graph is one in which every edge e is assigned a nonnegative number w(e), called the weight of e. The weight of a cycle is defined as the sum of the weights of its edges. The weighted degree of a vertex is the sum of the weights of the edges incident with it. In this paper, we prove that: Let G be a k-connected weighted graph with k?2. Then G contains either a Hamilton cycle or a cycle of weight at least 2m/(k+1), if G satisfies the following conditions: (1) The weighted degree sum of any k+1 pairwise nonadjacent vertices is at least m; (2) In each induced claw and each induced modified claw of G, all edges have the same weight. This generalizes an early result of Enomoto et al. on the existence of heavy cycles in k-connected weighted graphs. 相似文献
20.
Given a sample graphH and two integers,n andr, we colourK n byr colours and are interested in the following problem. Which colourings of the subgraphs isomorphic to H in K n must always occur (and which types of colourings can occur whenK n is coloured in an appropriate way)? These types of problems include theRamsey theory, where we ask: for whichn andr must a monochromaticH occur. They also include theanti-Ramsey type problems, where we are trying to ensure a totally multicoloured copy ofH, that is, anH each edge of which has different colour. 相似文献