Infinite subgraphs as matroid circuits

A matroidal family $\text{C}$ is defined to be a collection of graphs such that, for any given graph G, the subgraphs of G isomorphic to a graph in $\text{C}$ satisfy the matroid circuit-axioms. Here matroidal families closed under homeomorphism are considered. A theorem of Simöes-Pereira shows that when only finite connected graphs are allowed as members of $\text{C}$, two matroids arise: the cycle matroid and bicircular matroid. Here this theorem is generalized in two directions: the graphs are allowed to be infinite, and they are allowed to be disconnected. In the first case four structures result and in the second case two infinite families of matroids are obtained. The main theorem concerns the structures resulting when both restrictions are relaxed simultaneously.     

Matroidal families of finite connected nonhomeomorphic graphs exist

A matroidal family is a nonempty set ? of connected finite graphs such that for every arbitrary finite graph G the edge sets of the subgraphs of G which are isomorphic to an element of ? form a matroid on the edge set of G. In the present paper the question whether there are any matroidal families besides the four previously described by Simões-Pereira is answered affirmatively. It is shown that for every natural number n ? 2 there is a matroidal family that contains the complete graph with n vertices. For n = 4 this settles Simões-Pereira's conjecture that there is a matroidal family containing all wheels.     

Characterizing 3‐connected planar graphs and graphic matroids

A well‐known result of Tutte states that a 3‐connected graph G is planar if and only if every edge of G is contained in exactly two induced non‐separating circuits. Bixby and Cunningham generalized Tutte's result to binary matroids. We generalize both of these results and give new characterizations of both 3‐connected planar graphs and 3‐connected graphic matroids. Our main result determines when a natural necessary condition for a binary matroid to be graphic is also sufficient. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 165–174, 2010     

A composition for matroids

The composition of a quotient matroid Q over a collection of component matroids f₁, …, f_n indexed on the cells of Q, is described. This composition, called quotient composition, may be viewed as an application of clutter composition to matroids, or as a generalization of matroid direct sum composition to the next higher connectivity. It may also be viewed as equivalent to compositions described by Minty in 1966, and Brylawski in 1971.Quotient composition is characterized, and the circuits and rank function of a composed matroid are given. Various other properties are described, along with a category for quotient composition.     

Matroid representation of clique complexes

In this paper, we approach the quality of a greedy algorithm for the maximum weighted clique problem from the viewpoint of matroid theory. More precisely, we consider the clique complex of a graph (the collection of all cliques of the graph) which is also called a flag complex, and investigate the minimum number k such that the clique complex of a given graph can be represented as the intersection of k matroids. This number k can be regarded as a measure of “how complex a graph is with respect to the maximum weighted clique problem” since a greedy algorithm is a k-approximation algorithm for this problem. For any k>0, we characterize graphs whose clique complexes can be represented as the intersection of k matroids. As a consequence, we can see that the class of clique complexes is the same as the class of the intersections of partition matroids. Moreover, we determine how many matroids are necessary and sufficient for the representation of all graphs with n vertices. This number turns out to be n-1. Other related investigations are also given.     

On the existence of uncountably many matroidal families

A matroidal family is a set $\text{F}$ ≠ ? of connected finite graphs such that for every finite graph G the edge-sets of those subgraphs of G which are isomorphic to some element of $\text{F}$ are the circuits of a matroid on the edge-set of G. Simões-Pereira [5] shows the existence of four matroidal families and Andreae [1] shows the existence of a countably infinite series of matroidal families. In this paper we show that there exist uncountably many matroidal families. This is done by using an extension of Andreae's theorem, a construction theorem, and certain properties of regular graphs. Moreover we observe that all matroidal families so far known can be obtained in a unified way.     

Vector representable matroids of given rank with given automorphism group

A simple way of associating a matroid of prescribed rank with a graph is shown. The matroids so constructed are representable over any sufficiency large field. Their use is demonstrated by the following result: Given an integer k?3 and a function G associating a group with each subset of a set S, there is a matroid M(E), representable over any sufficiently large field, such that E ? S, and for any T ?/ S, the rank of M/Tis k, and the automorphine group of MT is isomorphic to G(T).     

Maximum Δ‐edge‐colorable subgraphs of class II graphs

A graph G is class II, if its chromatic index is at least Δ + 1. Let H be a maximum Δ‐edge‐colorable subgraph of G. The paper proves best possible lower bounds for |E(H)|/|E(G)|, and structural properties of maximum Δ‐edge‐colorable subgraphs. It is shown that every set of vertex‐disjoint cycles of a class II graph with Δ≥3 can be extended to a maximum Δ‐edge‐colorable subgraph. Simple graphs have a maximum Δ‐edge‐colorable subgraph such that the complement is a matching. Furthermore, a maximum Δ‐edge‐colorable subgraph of a simple graph is always class I. © 2011 Wiley Periodicals, Inc. J Graph Theory     

A characterization of orthogonal duality in matroid theory

An operation on matroids is a function defined from the collection of all matroids on finite sets to itself which preserves isomorphism of matroids and sends a matroid on a set S to a matroid on the same set S. We show that orthogonal duality is the only non-trivial operation on matroids which interchanges contraction and deletion.     

Netlike partial cubes, V: Completion and netlike classes

We define a completion of a netlike partial cube G by replacing each convex 2n-cycle C of G with n≥3 by an n-cube admitting C as an isometric cycle. We prove that a completion of G is a median graph if and only if G has the Median Cycle Property (MCP) (see N. Polat, Netlike partial cubes III. The Median Cycle Property, Discrete Math.). In fact any completion of a netlike partial cube having the MCP is defined by a universal property and turns out to be a minimal median graph containing G as an isometric subgraph. We show that the completions of the netlike partial cubes having the MCP preserves the principal constructions of these graphs, such as: netlike subgraphs, gated amalgams and expansions. Conversely any netlike partial cube having the MCP can be obtained from a median graph by deleting some particular maximal finite hypercubes. We also show that, given a netlike partial cube G having the MCP, the class of all netlike partial cubes having the MCP whose completions are isomorphic to those of G share different properties, such as: depth, lattice dimension, semicube graph and crossing graph.     

Coherent orientations and series-parallel networks

Let p be an edge of the graph G. An orientation of G is p-coherent if the set of directed circuits is exactly the set of circuits containing the edge p. Theorem: A matroidally connected graph G is a series-parallel network if and only if for every edge p of G, there exists a p-coherent orientation.     

Total domination critical and stable graphs upon edge removal

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. A graph is total domination edge critical if the removal of any arbitrary edge increases the total domination number. On the other hand, a graph is total domination edge stable if the removal of any arbitrary edge has no effect on the total domination number. In this paper, we characterize total domination edge critical graphs. We also investigate various properties of total domination edge stable graphs.     

Matroid basis graphs. I

A matroid may be defined as a collection of sets, called bases, which satisfy a certain exchange axiom. The basis graph of a matroid has a vertex for each basis and an edge for each pair of bases that differ by the exchange of a single pair of elements. Two characterizations of basis graphs are obtained. The first involves certain local subgraphs and how they lie when the given graph is leveled with respect to distance from a particular vertex. The second involves the existence of a special mapping from the given graph to some “full” basis graph. It is also shown that in a natural sense all basis graphs are homotopically trivial.     

Properties of matroids characterizable in terms of excluded matroids

Some properties π of matroids are characterizable in terms of a set S(π) of exluded matroids, that is, a matroid M satisfies property π if and only if M has no minor (series-minor, parallel-minor) isomorphic to a matroid in S(π). This note presents a necessary and sufficient condition for a property to be characterizable in terms of excluded 3-connected matroids.     

Pseudograph associahedra

Given a simple graph G, the graph associahedron KG is a simple polytope whose face poset is based on the connected subgraphs of G. This paper defines and constructs graph associahedra in a general context, for pseudographs with loops and multiple edges, which are also allowed to be disconnected. We then consider deformations of pseudograph associahedra as their underlying graphs are altered by edge contractions and edge deletions.     

On end degrees and infinite cycles in locally finite graphs

We introduce a natural extension of the vertex degree to ends. For the cycle space C(G) as proposed by Diestel and Kühn [4, 5], which allows for infinite cycles, we prove that the edge set of a locally finite graph G lies in C(G) if and only if every vertex and every end has even degree. In the same way we generalise to locally finite graphs the characterisation of the cycles in a finite graph as its 2-regular connected subgraphs.     

Some results related to the toughness of 3-domination critical graphs

A graph G is said to be k-γ-critical if the size of any minimum dominating set of vertices is k, but if any edge is added to G the resulting graph can be dominated with k−1 vertices. The structure of k-γ-critical graphs remains far from completely understood, even in the special case when the domination number γ=3. In a 1983 paper, Sumner and Blitch proved a theorem which may regarded as a result related to the toughness of 3-γ-critical graphs which says that if S is any vertex cutset of such a graph, then G−S has at most |S|+1 components. In the present paper, we improve and extend this result considerably.     

Optimal implementation of selectors in a data-base

The records of a data base can be accessed from other records or from a set of data items (inverted access, primary and secondary index of IMS, search keys of CODASYL etc.) which we call selectors. The implementation of this selectors can use different techniques as hash coding, inverted lists or hierarchical index (indexed sequential, B-trees etc…) We consider here the last one and we search for a given set of selectors an optimal index structure. We show how this problem can be put as the search of an optimal rooted tree among the partial subgraphs of a given graph G (this problem is known in graph theory as Steiner problem) and we give several properties which allow the graph G to be notabily reduced. Then we present a branch and bound algorithm to solve this problem.     

Connectivity in bicircular matroids

Tutte has defined n-connection for matroids and proved a connected graph is n-connected if and only if its polygon matroid is n-connected. In this paper we introduce a new notion of connection in graphs, called n-biconnection, and prove an analogous theorem for graphs and their bicircular matroids. Results concerning 3-biconnected graphs are also presented.