Biased graphs whose matroids are special binary matroids

Abiased graph is a graph together with a class of polygons such that no theta subgraph contains exactly two members of the class. To a biased graph are naturally associated three edge matroids:G(), L(), L ₀ (). We determine all biased graphs for which any of these matroids is isomorphic to the Fano plane, the polygon matroid ofK ₄,K ₅ orK _3,3, any of their duals, Bixby's regular matroidR ₁₀, or the polygon matroid ofK _m form > 5. In each case the bias is derived from edge signs. We conclude by finding the biased graphs for whichL ₀ () is not a graphic [or, regular matroid but every proper contraction is.Research supported by National Science Foundation grant DMS-8407102 and SGPNR grant 85Z0701Visiting Research Fellow, 1984–1985     

Graphs whose powers are chordal and graphs whose powers are interval graphs

The main theorem of this paper gives a forbidden induced subgraph condition on G that is sufficient for chordality of G^m. This theorem is a generalization of a theorem of Balakrishnan and Paulraja who had provided this only for m = 2. We also give a forbidden subgraph condition on G that is sufficient for chordality of G^2m. Similar conditions on G that are sufficient for G^m being an interval graph are also obtained. In addition it is easy to see, that no family of forbidden (induced) subgraphs of G is necessary for G^m being chordal or interval graph. © 1997 John Wiley & Sons, Inc.     

On the matroids in which all hyperplanes are binary

In this paper, it is shown that, for a minor-closed class of matroids, the class of matroids in which every hyperplane is in is itself minor-closed and has, as its excluded minors, the matroids U_1.1 N such that N is an excluded minor for . This result is applied to the class of matroids of the title, and several alternative characterizations of the last class are given.     

The circuit basis in binary matroids

The concept of a circuit basis for a matroid is introduced, as an algorithmically rapid way of determining several characteristics of a given matroid. It is used to give a short search for planarity in graphs, and also to begin the answer to a question of G.-C. Rota about “dependency among dependencies.” A circuit basis for a matroid is a least set of circuits which will generate all the circuits of the matroid by repeated use of symmetric differences of cells.     

Infinite matroids in graphs

It has recently been shown that infinite matroids can be axiomatized in a way that is very similar to finite matroids and permits duality. This was previously thought impossible, since finitary infinite matroids must have non-finitary duals.In this paper we illustrate the new theory by exhibiting its implications for the cycle and bond matroids of infinite graphs. We also describe their algebraic cycle matroids, those whose circuits are the finite cycles and double rays, and determine their duals. Finally, we give a sufficient condition for a matroid to be representable in a sense adapted to infinite matroids. Which graphic matroids are representable in this sense remains an open question.     

Degrees in a digraph whose nodes are graphs

By an f-graph we mean an unlabeled graph having no vertex of degree greater than f. Let D(n, f) denote the digraph whose node set is the set of f-graphs of order n and such that there is an arc from the node corresponding to graph H to the node corresponding to the graph K if and only if K is obtainable from H by the addition of a single edge. In earlier work, algorithms were developed which produce exact results about the structure of D(n, f), nevertheless many open problems remain. For example, the computation of the order and size of D(n, f) for a number of values of n and f have been obtained. Formulas for the order and size for f = 2 have also been derived. However, no closed form formulas have been determined for the order and size of D(n, f) for any value of f. Here we focus on questions concerning the degrees of the nodes in D(n,n − 1) and comment on related questions for D(n,f) for 2 f < n − 1.     

A note on graphs whose neighborhoods are n-cycles

Let G be a graph, and let v be a vertex of G. We denote by N(v) the set of vertices of G which are adjacent to v, and by 〈N(v)〉 the subgraph of G induced by N(v). We call 〈N(v)〉 the neighborhood of v. In a paper of 1968, Agakishieva has, as one of her main theorems, the statement: “Graphs in which every neighborhood is an n-cycle exist if and only if 3?n?6.” It it is the object of this note to provide a list of counter examples to this statement.     

Decomposition of binary matroids

We prove results relating to the decomposition of a binary matroid, including its uniqueness when the matroid is cosimple. We extend the idea of “freedom” of an element in a matroid to “freedom” of a set, and show that there is a unique maximal integer polymatroid inducing a given binary matroid.     

The inverse eigenvalue problem for Hermitian matrices whose graphs are cycles

In 1979, Ferguson characterized the periodic Jacobi matrices with given eigenvalues and showed how to use the Lanzcos Algorithm to construct each such matrix. This article provides general characterizations and constructions for the complex analogue of periodic Jacobi matrices. As a consequence of the main procedure, we prove that the multiplicity of an eigenvalue of a periodic Jacobi matrix is at most 2.     

Characterizing binary simplical matroids

In an earlier paper we defined a class of matroids whose circuit are combinatorial generalizations of simple polytopes; these matroids are the binary analogue of the simplical geometrics of Crapo and Rota. Here we find necessary and sufficient conditions for a matroid to be isomorphic to such a binary simplical matroid.     

Equivalent factor matroids of graphs

The factor matroid of a graphG is the matric matroid of the vertex-edge incidence matrix ofG interpreted over the real numbers. This paper presents a constructive characterization of the graphs hat have the same factor matroid as a given 4-connected bipartite graph.Research partially supported by NSF Grant ESS-8307796 and Office of Naval Research Grant N00014-86-K-0689.     

The Euler circuit theorem for binary matroids

It is proved that, if M is a binary matroid, then every cocircuit of M has even cardinality if and only if M can be obtained by contracting some other binary matroid M⁺ onto a single circuit. This is the natural analog of the Euler circuit theorem for graphs. It is also proved that every coloop-free matroid can be obtained by contracting some other matroid (not in general binary) onto a single circuit.     

Infinite graphs and bicircular matroids

B-matroids are a class of pre-independence spaces which retain many important properties of independence spaces. Higgs has shown that an infinite generalization of the cycle matroid of a finite graph which admits two-way infinite paths as circuits need not be a B-matroid. In this note it is shown that a similar generalization of the finite bicircular matroid is a ways a B-matroid.     

Inseparability graphs of oriented matroids

We determine the inseparability graphs of uniform oriented matroids and of graphic oriented matroids. For anyr, n such that 4rn–3, examples of rankr uniform oriented matroids onn elements with a given inseparability graph are obtained by simple constructions of polytopes having prescribed separation properties.     

A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs

The theta bodies of a polynomial ideal are a series of semidefinite programming relaxations of the convex hull of the real variety of the ideal. In this paper we construct the theta bodies of the vanishing ideal of cycles in a binary matroid. Applied to cuts in graphs, this yields a new hierarchy of semidefinite programming relaxations of the cut polytope of the graph. If the binary matroid avoids certain minors we can characterize when the first theta body in the hierarchy equals the cycle polytope of the matroid. Specialized to cuts in graphs, this result solves a problem posed by Lovász.     

Note on binary simplicial matroids

Using an earlier characterization of simplicial hypergraphs we obtain a characterization of binary simplicial matroids in terms of the existence of a special base.     

Separating cocircuits in binary matroids

A cocircuit of a matroid is separating if deleting it leaves a separable matroid. We give an effecient algorithm which finds a separating cocircuit or a Fano minor in a binary matroid, thus proving constructively a theorem of Tutte. Using this algorithm and a new recursive characterization of bond matroids, we give a new method for testing binary matroids for graphicness. We also give an efficient algorithm for finding a special kind of separating cocircuit: one whose deletion leaves a matroid having a coloop.     

Connected hyperplanes in binary matroids

For a 3-connected binary matroid M, let dim_A(M) be the dimension of the subspace of the cocycle space spanned by the non-separating cocircuits of M avoiding A, where A⊆E(M). When A=∅, Bixby and Cunningham, in 1979, showed that dim_A(M)=r(M). In 2004, when |A|=1, Lemos proved that dim_A(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 2dim_A(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.