准模糊图拟阵基的交换

本文讨论了准模糊图拟阵基的交换定理,在此基础上给出了基有序的准模糊图拟阵的一些性质.     

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

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

Cycles in Circuit Graphs of Matroids

Let G be the circuit graph of any connected matroid. We prove that G is edge-pancyclic if it has at least three vertices. This work is supported by the National Natural Science Foundation(60673047) and the Doctoral Program Foundation of Education Ministry (20040422004) of China.     

n圈中辐图的团覆盖数和团划分数

本文主要讨论 Petersen图的一类推广图—— n圈中辐图的团覆盖数和团划分数 ,由此得出该图的团覆盖数和团划分数相等的结论 ,同时给出了其在不同情况下的计算公式 .     

Dihedral Hamiltonian Cycle Systems of the Cocktail Party Graph

The existence problem for a Hamiltonian cycle decomposition of (the so called cocktail party graph) with a dihedral automorphism group acting sharply transitively on the vertices is completely solved. Such Hamiltonian cycle decompositions exist for all even n while, for n odd, they exist if and only if the following conditions hold: (i) n is not a prime power; (ii) there is a suitable ? such that (mod 2^?) for all prime factors p of n and the number of the prime factors (counted with their respective multiplicities) such that (mod ) is even. Thus in particular one has a dihedral Hamiltonian cycle decomposition of the cocktail party graph on 8k vertices for all k, while it is known that no such cyclic Hamiltonian cycle decomposition exists. Finally, this paper touches on a recently introduced symmetry requirement by proving that there exists a dihedral and symmetric Hamiltonian cycle system of if and only if (mod 4).     

On Recognizing Frame and Lifted‐Graphic Matroids

We prove that there is no polynomial with the property that a matroid M can be determined to be either a lifted‐graphic or frame matroid using at most rank evaluations. This resolves two conjectures of Geelen, Gerards, and Whittle (Quasi‐graphic matroids, to appear in J. Graph Theory).     

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…     

Orientable Hamilton Cycle Embeddings of Complete Tripartite Graphs II: Voltage Graph Constructions and Applications

In an earlier article the authors constructed a hamilton cycle embedding of in a nonorientable surface for all and then used these embeddings to determine the genus of some large families of graphs. In this two‐part series, we extend those results to orientable surfaces for all . In part II, a voltage graph construction is presented for building embeddings of the complete tripartite graph on an orientable surface such that the boundary of every face is a hamilton cycle. This construction works for all such that p is prime, completing the proof started by part I (which covers the case ) that there exists an orientable hamilton cycle embedding of for all , . These embeddings are then used to determine the genus of several families of graphs, notably for and, in some cases, for .     

The Lattice of Cyclic Flats of a Matroid

A flat of a matroid is cyclic if it is a union of circuits. The cyclic flats of a matroid form a lattice under inclusion. We study these lattices and explore matroids from the perspective of cyclic flats. In particular, we show that every lattice is isomorphic to the lattice of cyclic flats of a matroid. We give a necessary and sufficient condition for a lattice of sets and a function to be the lattice of cyclic flats of a matroid and the restriction of the corresponding rank function to . We apply this perspective to give an alternative view of the free product of matroids and we show how to compute the Tutte polynomial of the free product in terms of the Tutte polynomials of the constituent matroids. We define cyclic width and show that this concept gives rise to minor-closed, dual-closed classes of matroids, two of which contain only transversal matroids. Received May 29, 2005     

一类泛圈图

本文证明了如果 Ｇ 是 ２ 连通无爪图, Ｇ 不是圈,ｎ＝ ｜ Ｖ（ Ｇ）｜≥９, Ｇ 的每个导出子图 Ａ都满足φ（ａ１,ａ２ ）,且 Ｇ 中不含同构于 Ｚ＋２ 的导出子图,则 Ｇ是泛圈图     

完全偶图的圈基内插性质

图G的一个圈基的长度是该圈基的所有圈的长度之和。设C^-、C^ 分别是G的最小、最大圈基长度,如果对任一偶数C,C^-＜C＜C^ ,都存在G的一个长为C的圈基,则称G具有偶圈基内插性质,本证明了,完全偶图Km,n具有偶圈基内插性质。     

The Greedy Algorithm and Coxeter Matroids

The notion of matroid has been generalized to Coxeter matroid by Gelfand and Serganova. To each pair (W, P) consisting of a finite irreducible Coxeter group W and parabolic subgroup P is associated a collection of objects called Coxeter matroids. The (ordinary) matroids are a special case, the case W = A (isomorphic to the symmetric group Sym_{_n+1}) and P a maximal parabolic subgroup. The main result of this paper is that for Coxeter matroids, just as for ordinary matroids, the greedy algorithm provides a solution to a naturally associated combinatorial optimization problem. Indeed, in many important cases, Coxeter matroids are characterized by this property. This result generalizes the classical Rado-Edmonds and Gale theorems.A corollary of our theorem is that, for Coxeter matroids L, the greedy algorithm solves the L-assignment problem. Let W be a finite group acting as linear transformations on a Euclidean space , and let

一个五阶图与路、圈的联图的交叉数

目前已经确定的两个图的联图的交叉数结果较少.设H是由一个4圈及一个孤立点所构成的5阶图.研究了图H与路、圈的联图的交叉数,得到了cr(H+P_n)=Z(5,n)+[n/2]+l,cr(H+C_n):Z(5,n)+[n/2]+2,其中,P_n与C_n分别表示含n个顶点的路与圈.     

On Matroids and Orlik-Solomon Algebras

In this paper we axiomatize combinatorics of arrangements of affine hyperplanes, which is a generalization of matroids, called quasi-matroids. We show that quasi-matroids are equivalent to pointed matroids. On the other hand, the Orlik-Solomon (OS) algebra of a quasimatroid can be constructed. We prove that the OS algebra of a quasi-matroid is isomorphic to the direct image of the OS algebra of a matroid by the linear derivation.AMS Subject Classification: 03B35, 13D03, 52C35.     

On the Location of Roots of Graph Polynomials

Roots of graph polynomials such as the characteristic polynomial, the chromatic polynomial, the matching polynomial, and many others are widely studied. In this paper we examine to what extent the location of these roots reflects the graph theoretic properties of the underlying graph.     

任意基数集上的拟阵之单扩张

对于由Betten和Wenzel于2003年提出的任意基数集上的拟阵其相应的秩公理给予了证明,并将此结果用于研究任意基数集上的拟阵的单扩张问题.     

关于乘积图的二维带宽问题

给出一般乘积图的二维带宽的界，并解决一类乘积图的二维带宽问题．最后给出完全ｋ部图的二维带宽。