Applications of matroid partition to tree decomposition

1.IntroductionWeshallassumefamiliaritywithmatroidtheory--foranintroduction,andforthedefinitionoftermsnotdefinedinthispaper,see[31.Edmonds'matroidpartitiontheoremisaveryimportanttheorem,whichhasmanyapplications.Twoclassicresultsof[4,5],whichconcernwithpackingandcoveringoftheedgesetofagraphwithkedge--disjointspanningtrees,canbeeasilydeducedfromit(see[3],PP.125--127).Inthepresentpaperwewillpresentamatroidapproachtotheproblemoftreedecompositionraisedrecently(see[6,7]).Ourmainaimistogivealternati…     

准模糊图拟阵基图的最大权基与字典序最大的基

模糊拟阵的基图是模糊拟阵的基本概念.在准模糊图拟阵的基础上,给出了准模糊图拟阵基图的最大权基与字典序最大的基的性质,这将有利于模糊拟阵从基础研究逐渐转向应用研究.     

The equivariant topology of stable Kneser graphs

The stable Kneser graph SG_n,k, n?1, k?0, introduced by Schrijver (1978) [19], is a vertex critical graph with chromatic number k+2, its vertices are certain subsets of a set of cardinality m=2n+k. Björner and de Longueville (2003) [5] have shown that its box complex is homotopy equivalent to a sphere, Hom(K₂,SG_n,k)?Sk. The dihedral group D2m acts canonically on SG_n,k, the group C₂ with 2 elements acts on K₂. We almost determine the (C₂×D2m)-homotopy type of Hom(K₂,SG_n,k) and use this to prove the following results.The graphs SG_2s,4 are homotopy test graphs, i.e. for every graph H and r?0 such that Hom(SG_2s,4,H) is (r−1)-connected, the chromatic number χ(H) is at least r+6.If k∉{0,1,2,4,8} and n?N(k) then SG_n,k is not a homotopy test graph, i.e. there are a graph G and an r?1 such that Hom(SG_n,k,G) is (r−1)-connected and χ(G)<r+k+2.     

On the Circuit-cocircuit Intersection Conjecture

Oxley has conjectured that for k≥4, if a matroid M has a k-element set that is the intersection of a circuit and a cocircuit, then M has a (k−2)-element set that is the intersection of a circuit and a cocircuit. In this paper we prove a stronger version of this conjecture for regular matroids. We also show that the stronger result does not hold for binary matroids. The second author was partially supported by CNPq (grant no 302195/02-5) and the ProNEx/CNPq (grant no 664107/97-4).     

The connectivity and minimum degree of circuit graphs of matroids

Let G be the circuit graph of any connected matroid M with minimum degree 5（G）. It is proved that its connectivity κ（G） ≥2｜E（M） - B（M）｜ - 2. Therefore 5（G） ≥ 2｜E（M） - B（M）｜ - 2 and this bound is the best possible in some sense.     

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.     

Equipartite Gregarious 5-Cycle Systems and Other Results

A k-cycle decomposition of a complete multipartite graph is said to be gregarious if each k-cycle in the decomposition has its vertices in k different partite sets. Equipartite 3-cycle systems are 3-GDDs (and so are automatically gregarious), and necessary and sufficient conditions for their existence are known. The cases of equipartite gregarious 4-, 6- and 8-cycle systems have also been dealt with (using techniques that could be applied in the case of any even length cycle). Here we give necessary and sufficient conditions for the existence of a gregarious 5-cycle decomposition of the complete equipartite graph K_m(n) (in effect the first odd length cycle case for which the gregarious constraint has real meaning). In doing so, we also define some general cyclic constructions for the decomposition of certain complete equipartite graphs into gregarious p-cycles (where p is an odd prime).     

Circuit and cocircuit partitions of binary matroids

We give an example of a class of binary matroids with a cocircuit partition and we give some characteristics of a set of cocircuits of such binary matroids which forms a partition of the ground set.     

Equipartite gregarious 6- and 8-cycle systems

A k-cycle decomposition of a complete multipartite graph is said to be gregarious if each k-cycle in the decomposition has its vertices in k different partite sets. Equipartite gregarious 3-cycle systems are 3-GDDs, and necessary and sufficient conditions for their existence are known (see for instance the CRC Handbook of Combinatorial Designs, 1996, C.J. Colbourn, J.H. Dinitz (Eds.), Section III 1.3). The cases of equipartite and of almost equipartite 4-cycle systems were recently dealt with by Billington and Hoffman. Here, for both 6-cycles and for 8-cycles, we give necessary and sufficient conditions for existence of a gregarious cycle decomposition of the complete equipartite graph K_n(a) (with n parts, n?6 or n?8, of size a).     

障碍拟阵图

Let G be a simple graph and T={S :S is extreme in G}. If M(V(G), T) is a matroid, then G is called an extreme matroid graph. In this paper, we study the properties of extreme matroid graph.     

Monotone labelings in polygonal tilings

Labeling the vertices of a finite sequence of polygonal tilings with fewest monotonicity violations enables to represent the tilings by merely specifying sets of vertices—the sequences of their appearance results from the labels. Eventually, this allows a lossless data compression for the sequence of tilings.The existence and computation of suitable labelings is derived from matching and graph colorings which induce an order on the tilings. This order is series-parallel on each individual tiling.     

The toughness of split graphs

In this short note we argue that the toughness of split graphs can be computed in polynomial time. This solves an open problem from a recent paper by Kratsch et al. (Discrete Math. 150 (1996) 231–245).     

Unipancyclic matroids

Analogous to the concept of uniquely pancyclic graphs, we define a uniquely pancyclic (UPC) matroid of rank $r$ to be a (simple) rank-$r$ matroid containing exactly one circuit of each length $?$ for $3\le ?\le r+1$. Our discussion addresses the existence of graphic, binary, and transversal representations of UPC matroids. Using Shi’s results, which catalogued exactly seven non-isomorphic UPC graphs, we produce a nongraphic binary UPC matroid of rank 24. We consider properties of binary UPC matroids in general, and prove that all binary UPC matroids have a connectivity of $2$.