Bonds Intersecting Cycles In A Graph

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.     

An Excluded-Minor Problem in Matroids

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     

Circuits and Cocircuits in Regular Matroids

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.     

On the Number of Bases of Bicircular Matroids

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 K_n or a complete bipartite graph K_n,m.Received April 25, 2003     

Graph Connectivity After Path Removal

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 ₁[u,v], P ₂[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     

The Penrose Polynomial of Binary Matroids

 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)     

Graph products and monochromatic multiplicities

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 ₄.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.     

Orientations of chain groups

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.     

Cycles in weighted graphs

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].     

On the Turán number for the hexagon

A long-standing conjecture of Erd?s and Simonovits is that ex(n,C_2k), 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

     

Covering odd cycles

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     

A note on the girth of digraphs

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.     

Matroids algebraic overF(t) are algebraic overF

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.     

On the number ofC 5′S in a triangle-free graph

Research partially supported bv Hungarian National Foundation for Scientific Research Grant no. 1812.     

Two Remarks Concerning Balanced Matroids

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.     

Graphs With 3n−6 Edges Not Containing A Subdivision Of K 5

We determine all graphs on n ≥ 3 vertices with 3n-6 edges which do not contain a subdivision of K₅. These are exactly the graphs which one gets from any number of disjoint maximal planar graphs by successively pasting along triangles.     

A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks

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.     

The maximum number of Hamiltonian paths in tournaments

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.     

Heavy cycles in k-connected weighted graphs with large weighted degree sums

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.     

On restricted colourings ofK n

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.