拟阵基的交图的性质
|
摘要
图论和拟阵理论在二十世纪经历了空前的发展.图论起源于著名的哥尼斯堡七桥问题.在图论的历史中,还有一个最著名的问题-四色问题.四色问题又称四色猜想,是世界近代三大数学难题之一.四色猜想的提出来自英国.1852年,毕业于伦敦大学的弗南西斯·格思里来到一家科研单位搞地图着色工作时,发现了一种有趣的现象：”看来,每幅地图都可以用四种颜色着色,使得有共同边界的国家都被着上不同的颜色.”1872年,英国当时最著名的数学家Cayley正式向伦敦数学学会提出了这个问题,于是四色猜想成了世界数学界关注的问题.世界上许多一流的数学家都纷纷参加了四色猜想的大会战.1878-1880年两年间,著名律师兼数学家Kapel和Taylor两人分别提交了证明四色猜想的论文,宣布证明了四色定理.但后来数学家Heawood以自己的精确计算指出肯普的证明是错误的.不久, Taylor的证明也被人们否定了.于是,人们开始认识到,这个貌似容易的题目,其实是一个可与费马猜想相媲美的难题.二十世纪三十年代,Whitney在他的论文中,作为对矩阵和向量的独立性的抽象概括,首次提出了拟阵的概念.同时,拟阵也抽象了很多图的性质.拟阵理论为组合优化问题和设计多项式算法提供了强有力的工具.图的支撑树及拟阵的基都是组合理论的基本研究对象.一个连通图的树图能够反映该图的不同支撑树之间的变换关系.因此,研究一个图的树图有助于我们更好地了解该图的性质.同样的一个拟阵的基图能够反映该拟阵的不同基之间的变换关系.因此,研究一个拟阵的基图有助于我们更好地了解该拟阵的性质.近些年来,树图和拟阵的基图被推广得到了一些新的图类为了研究拟阵中圈的性质,P.Li和G.Liu提出了拟阵圈图的概念,并且研究了拟阵圈图的连通度,圈图中的路和圈的性质.为了进一步研究拟阵中基的性质,Y.Zhang和G.Liu提出了拟阵基的交图的概念.
设G是一个图,图G的点集和边集分别记为V(G)和E(G).包含G的每个点的路称为G的一条哈密尔顿路；同样的,包含G的每个点的圈称为G的一个哈密尔顿圈.如果一个图存在一个哈密尔顿圈,则称之为哈密尔顿的.如果对于一个图G的任意两个顶点来说,G都有一条哈密尔顿路连接他们,则称G是哈密尔顿连通的.如果对一个图G的任意一条边来说,G都有一个含这条边的哈密尔顿圈,则称G是边哈密尔顿的,或者称G是正哈密尔顿的,写作G∈H+.如果对一个图G的任意一条边来说,G都有一个不包含这条边的哈密尔顿圈,则称G是负哈密尔顿的,写作G∈H-.如果G既是正哈密尔顿的,又是负哈密尔顿的,我们称G是一致哈密尔顿的.
一个拟阵M就是对于一个有限集E,令I为集合E中非空子集族,它满足如下的条件：(I1)(?)∈I(12)若I2∈I且I1(?)I2,则I1∈I;(13)若I1,I2∈I并且|I1|<|I2|,则存在e∈I2\I1,使得I1∪{e}∈I.
那么我们称M=(E,I)为定义在有限集E上的拟阵.当I∈Z(M),我们称I为M的一个独立集.对于不在Z中E的子集,我们称之为相关集.极小的相关集称为拟阵的圈,我们可以用拟阵的圈集合去定义拟阵.
令E为一个含有有限个元素的集合.令C为集合E中非空子集族,它满足如下的公理：(C1)(?)C;(C2)若C1,C2∈C且C1∈C2,则C1=C2；(C3)若C1≠C2,C1,C2∈C并且存在e∈C1∩C2,则恒有C3∈C满足C3∈(C1∪C2)-e.
拟阵M的一个极大独立集被称为拟阵M的基,表示为B(M).拟阵M中一个基B(M)的元素个数定义为拟阵M的秩.令B(M)表示拟阵M中基的集合.同样我们也可以用拟阵的基来定义拟阵：(B1)所有的基的基数相同；(B2)如果B1,B2∈B且x∈B1,则存在y∈B2,使得(B1\{x})∪{y}∈B.
拟阵M=(E,B)的基图是这样的一个图G,其中V(G)=B,E(G)={BB'|B,B'∈B,|B\B'|=1},注意在这里图G的顶点和M的基用同样的符号表示.
现在我们给出拟阵基的交图的概念.定义拟阵M的基的交图G=G(M)的顶点集V(G)=B,边集E(G)={BB'|B,B'∈B,|B∩B'|≠0}这里B和B’既代表G的顶点,也代表M的基.
下面我们给出整数流,也就是处处非零的k-流的定义：
给定一个图G,设D为图G的一个方向,设函数f:E(G)→Z,使得-k 设图G是无向图,A是一个非平凡的阿贝尔加群(单位元为0),A*是A中非零元素所构成的集合.我们定义F(G,A)={f|f:E(G)→4)和F*(G,A)={f|f:E(G)→A*).对于每一个f∈F(G,A),f的边界函数(?)f(v):V(G)→A的定义如下：其中“∑”指的是阿贝尔群里的加法.我们定义一个图G的处处非零A-流(简称A-NZF)指的是一个函数f∈F*(G,A)使得(?)f=0成立.如果一个图G有一个处处非零的k-流当且仅当图G有一个处处非零的Zk-流.
对于任意的b∈Z(G,A),如果有一个函数f∈F*(G,A)使得af=b成立,那么我们称f是一个处处非零(A,b)-流(简称(A,b)-NZF).
Jaeger等人推广了整数流的概念,提出了A-连通的概念,一个无向图G称为A-连通的,如果G的每一个定向G’对于每一个函数b∈Z(G',A),都存在一个(A,b)一NZF,记作G∈(A).同样的,G有A-NZF当G有定向G’使得G’有A-NZF.A-连通性的概念是Jaeger等人在[31]中提出的,A-NZF与A-连通性有密切关联.
本文主要研究的是拟阵基的交图的一致哈密尔顿性,边不交的哈密尔顿圈个数,图中顶点不交的圈以及拟阵基图的整数流性质,全文共分为四章.
第一章给出了一个相对完整的简介.首先介绍一些图论中的基本术语和定义,然后给出了关于树图,拟阵基图以及森林图的一个简短但相对完整的综述,并介绍了拟阵基的交图和整数流的研究现状,最后,给出了本文的主要结论.
第二章我们研究了拟阵基的交图中的哈密尔顿圈.首先我们给出了一个对于拟阵基的交图的简短的介绍.然后我们证明了拟阵基的交图的一致哈密尔顿性,接着我们还继续证明了简单拟阵的拟阵基的交图有两条边不交的哈密尔顿圈.
第三章主要讨论拟阵基的交图中顶点不交的圈的性质.同样的,首先,给出了对于拟阵基的交图的一个简短的介绍.然后我们讨论了拟阵基的交图中的顶点不交的圈的一些性质,并给出证明.
第四章主要讨论拟阵基图的整数流问题.在这一章里,我们首先给出了对于整数流和群连通度的一个简短的介绍以及一些已知的结论.之后,我们讨论了拟阵基图的群连通性以及拟阵基图上的处处非零的3-流,我们证明了简单拟阵的拟阵基图上有处处非零的3-流.
Graph theory and matroid theory have witnessed an unprecedented growth in the twentieth century. Graph theory originated in the famous prob-lem of the Seven Bridges of Konigsberg. Matroid theory dates from the1930's and Whitney in his basic paper conceived a matroid as an abstract general-ization of a matrix. Matroid theory gives us powerful techniques for under-standing combinatorial optimization problems and for designing polynomial-time algorithms. Meanwhile, matroid theory give an abstract generalization of trees of graph. Spanning trees of graphs and bases of matroids are basic objects in combinatorial theory. The tree graph of a connected graph can reflect the exchanging relationship of different spanning trees, so studying tree graphs is useful for us to learn more about the properties of a graph. Similarly, the base graph of a matroid can reflect the exchanging relation-ship of different bases, so studying base graphs is useful for us to learn more about the properties of a matroid. In recent years, many variations of tree graph and base graph are introduced. In order to study the properties of circuits of matroids, P. Li and G. Liu give the definition as circuit graph of a matroid, and prove some properties of this graph. We continue their research on exchanging relationship of different bases of matroids and give a new kind of graphs:Intersection graphs of bases of matroids.
Let E be a finite set and I be a collection of non-null subsets of E. If I satisfying the following axioms, we call (E,I) a matroid on E. (11)(?)∈I;(12) If I2∈I and I1C/2, then I1∈I;(13) If I1,I2∈I and|I1|<|I2|, there exists an element e∈I2\I1such that I1U{e}∈I.
Let C be a collection of non-null subsets of E which satisfies the following axioms:(C1)(?)∈C;(C2) If C1, C2∈C and C1(?)C2, then C1=C2;(C3) If C1≠C2, C1,C2∈C and for an element e∈C1∩C2, there exist C3∈C, such that C3C (C1∪C2)-e.
We refer to the members of C as circuits of the matroid M. The family of circuits of M determines a matroid.
A subset of E that does not contain any circuits is called an independent set of M. A maximal independent set is called a basis of M, denoted by B(M). Let B(M) denote the family of bases of M. Then it satisfies the following two axioms:(B1) All bases have the same number of elements.(B2) If B and B'are bases, and if b is an element of B, then there is an element b'∈B', such that B∪{b'}\{b} is also a basis.
A subset S of E is called a separator of M if every circuit of M is either contained in S or E-S. Union and intersection of two separators of M is also a separator of M. If0and E are the only separators of M, then M is said to be connected. The minimal non-empty separators of M are called the components of M.
If a circuit of M has only one element, then we call this circuit a loop of M. If a set of two elements{x, y} is a circuit of M, then we call the set{x, y} a pair of parallel elements, x and y are parallel to each other. A matroid is simple if it has no2-circuits and loops. We say that e is a coloop if it is not contained in any circuit of M. A coloop is a component of M.
Let G be a graph. The notation V(G) and E(G) will be used for the vertex-set and edge-set of G, respectively. A path that contains every vertex of G is called a Hamilton path of G; Similarly, a Hamilton cycle of G is a cycle that contains every vertex of G. A graph is hamiltonian if it contains a Hamilton cycle. A graph G is called Hamilton connected if every two vertices of G are connected by a Hamilton path. We now call a graph G positively Hamilton, written G∈H+, if every edge of G is in some Hamilton cycle; G is negatively Hamilton, written G∈H-, if for each edge of G there is a Hamilton cycle avoiding it. When∈G H+and G∈H-, we say that G is uniformly Hamilton. A graph G is also called edge-Hamiltonian if G is positively Hamilton.
The circuit graph of a matroid M is a graph G=G(M) with vertex set V(G) and edge set E(G) such that V(G)=C and E(G)={CC'}C, C'∈C,|C∩C'|≠0), where the same notation is used for the vertices of G and the circuits of M.
Let G be a graph with an orientation D. If an edge e∈E(G) is directed from vertex u to another vertex v, then the tail of e is u, the head of e is v. For each vertex v∈V(G), E+(v) is the set of edges with tail v, and E-(v) is the set of edges with head v. Let Zk denote the abelian group of k elements with identity0. Let F(G, Zk) be the set of all functions from E(G) to Zk. For any given function f∈F(G, Zk), let f is called a Zk-flow in G if (?)f(v)=0for each vertex v∈V(G). The support of f is defined by S(f)={e∈E(G)|f(e)≠0} and f is nowhere- zero if S(f)=E(G) which means that there exists no e E E(G) such that f(e)=0.
If we consider the case that F(G, Z) is the set of all functions from E(G) to Z, where Z denotes the set of integers. For an integer k>2, a nowhere-zero k-flow of G is an orientation D of G together with a function f∈F(G, Z) such that for each e∈E(G),0<|f(e)| Jaeger et al. introduced the notion of Zk-connectedness, which can be regarded as an extension of Zk-flows. A graph G is Zk-connected if for any function b from V(G) to Zk with∑v∈V(G) b(v)=0, there is a function f∈F(G, Zk)such that (?)f(v)=b(v) for each vertex v∈V(G). Clearly, if G is Zk-connected, then it has a nowhere-zero k-flow. But the converse is not true. This is why we introduce the notion of group connectivity here because we can solve the nowhere-zero3-flow problems through the properties of Z3-connectivity. Let (Zk) denoted the class of graphs which is Zk-connected.
The main content of this thesis is the Hamiltonian cycles in intersection graphs of bases of matroids, vertex disjoint cycles in intersection graphs of bases of matroids and nowhere-zero3-flow in intersection graphs of bases of matroids. The thesis is divided into four chapters.
In Chapter1, a short but relatively complete introduction about graph theory is given. First, we introduce some basic definitions and notations. And then we give a short survey about tree graphs, matroid base graphs and forest graphs. At last, we outline the main results of this thesis. In Chapter2, some properties of the Hamilton cycles in intersection graphs of bases of matroids are given. We discuss the vertex disjoint cycles in intersection graphs of bases of matroids in Chapter3. In Chapter4, we study the nowhere zero3-flows in matroid base graphs.
设G是一个图,图G的点集和边集分别记为V(G)和E(G).包含G的每个点的路称为G的一条哈密尔顿路；同样的,包含G的每个点的圈称为G的一个哈密尔顿圈.如果一个图存在一个哈密尔顿圈,则称之为哈密尔顿的.如果对于一个图G的任意两个顶点来说,G都有一条哈密尔顿路连接他们,则称G是哈密尔顿连通的.如果对一个图G的任意一条边来说,G都有一个含这条边的哈密尔顿圈,则称G是边哈密尔顿的,或者称G是正哈密尔顿的,写作G∈H+.如果对一个图G的任意一条边来说,G都有一个不包含这条边的哈密尔顿圈,则称G是负哈密尔顿的,写作G∈H-.如果G既是正哈密尔顿的,又是负哈密尔顿的,我们称G是一致哈密尔顿的.
一个拟阵M就是对于一个有限集E,令I为集合E中非空子集族,它满足如下的条件：(I1)(?)∈I(12)若I2∈I且I1(?)I2,则I1∈I;(13)若I1,I2∈I并且|I1|<|I2|,则存在e∈I2\I1,使得I1∪{e}∈I.
那么我们称M=(E,I)为定义在有限集E上的拟阵.当I∈Z(M),我们称I为M的一个独立集.对于不在Z中E的子集,我们称之为相关集.极小的相关集称为拟阵的圈,我们可以用拟阵的圈集合去定义拟阵.
令E为一个含有有限个元素的集合.令C为集合E中非空子集族,它满足如下的公理：(C1)(?)C;(C2)若C1,C2∈C且C1∈C2,则C1=C2；(C3)若C1≠C2,C1,C2∈C并且存在e∈C1∩C2,则恒有C3∈C满足C3∈(C1∪C2)-e.
拟阵M的一个极大独立集被称为拟阵M的基,表示为B(M).拟阵M中一个基B(M)的元素个数定义为拟阵M的秩.令B(M)表示拟阵M中基的集合.同样我们也可以用拟阵的基来定义拟阵：(B1)所有的基的基数相同；(B2)如果B1,B2∈B且x∈B1,则存在y∈B2,使得(B1\{x})∪{y}∈B.
拟阵M=(E,B)的基图是这样的一个图G,其中V(G)=B,E(G)={BB'|B,B'∈B,|B\B'|=1},注意在这里图G的顶点和M的基用同样的符号表示.
现在我们给出拟阵基的交图的概念.定义拟阵M的基的交图G=G(M)的顶点集V(G)=B,边集E(G)={BB'|B,B'∈B,|B∩B'|≠0}这里B和B’既代表G的顶点,也代表M的基.
下面我们给出整数流,也就是处处非零的k-流的定义：
给定一个图G,设D为图G的一个方向,设函数f:E(G)→Z,使得-k
对于任意的b∈Z(G,A),如果有一个函数f∈F*(G,A)使得af=b成立,那么我们称f是一个处处非零(A,b)-流(简称(A,b)-NZF).
Jaeger等人推广了整数流的概念,提出了A-连通的概念,一个无向图G称为A-连通的,如果G的每一个定向G’对于每一个函数b∈Z(G',A),都存在一个(A,b)一NZF,记作G∈(A).同样的,G有A-NZF当G有定向G’使得G’有A-NZF.A-连通性的概念是Jaeger等人在[31]中提出的,A-NZF与A-连通性有密切关联.
本文主要研究的是拟阵基的交图的一致哈密尔顿性,边不交的哈密尔顿圈个数,图中顶点不交的圈以及拟阵基图的整数流性质,全文共分为四章.
第一章给出了一个相对完整的简介.首先介绍一些图论中的基本术语和定义,然后给出了关于树图,拟阵基图以及森林图的一个简短但相对完整的综述,并介绍了拟阵基的交图和整数流的研究现状,最后,给出了本文的主要结论.
第二章我们研究了拟阵基的交图中的哈密尔顿圈.首先我们给出了一个对于拟阵基的交图的简短的介绍.然后我们证明了拟阵基的交图的一致哈密尔顿性,接着我们还继续证明了简单拟阵的拟阵基的交图有两条边不交的哈密尔顿圈.
第三章主要讨论拟阵基的交图中顶点不交的圈的性质.同样的,首先,给出了对于拟阵基的交图的一个简短的介绍.然后我们讨论了拟阵基的交图中的顶点不交的圈的一些性质,并给出证明.
第四章主要讨论拟阵基图的整数流问题.在这一章里,我们首先给出了对于整数流和群连通度的一个简短的介绍以及一些已知的结论.之后,我们讨论了拟阵基图的群连通性以及拟阵基图上的处处非零的3-流,我们证明了简单拟阵的拟阵基图上有处处非零的3-流.
Graph theory and matroid theory have witnessed an unprecedented growth in the twentieth century. Graph theory originated in the famous prob-lem of the Seven Bridges of Konigsberg. Matroid theory dates from the1930's and Whitney in his basic paper conceived a matroid as an abstract general-ization of a matrix. Matroid theory gives us powerful techniques for under-standing combinatorial optimization problems and for designing polynomial-time algorithms. Meanwhile, matroid theory give an abstract generalization of trees of graph. Spanning trees of graphs and bases of matroids are basic objects in combinatorial theory. The tree graph of a connected graph can reflect the exchanging relationship of different spanning trees, so studying tree graphs is useful for us to learn more about the properties of a graph. Similarly, the base graph of a matroid can reflect the exchanging relation-ship of different bases, so studying base graphs is useful for us to learn more about the properties of a matroid. In recent years, many variations of tree graph and base graph are introduced. In order to study the properties of circuits of matroids, P. Li and G. Liu give the definition as circuit graph of a matroid, and prove some properties of this graph. We continue their research on exchanging relationship of different bases of matroids and give a new kind of graphs:Intersection graphs of bases of matroids.
Let E be a finite set and I be a collection of non-null subsets of E. If I satisfying the following axioms, we call (E,I) a matroid on E. (11)(?)∈I;(12) If I2∈I and I1C/2, then I1∈I;(13) If I1,I2∈I and|I1|<|I2|, there exists an element e∈I2\I1such that I1U{e}∈I.
Let C be a collection of non-null subsets of E which satisfies the following axioms:(C1)(?)∈C;(C2) If C1, C2∈C and C1(?)C2, then C1=C2;(C3) If C1≠C2, C1,C2∈C and for an element e∈C1∩C2, there exist C3∈C, such that C3C (C1∪C2)-e.
We refer to the members of C as circuits of the matroid M. The family of circuits of M determines a matroid.
A subset of E that does not contain any circuits is called an independent set of M. A maximal independent set is called a basis of M, denoted by B(M). Let B(M) denote the family of bases of M. Then it satisfies the following two axioms:(B1) All bases have the same number of elements.(B2) If B and B'are bases, and if b is an element of B, then there is an element b'∈B', such that B∪{b'}\{b} is also a basis.
A subset S of E is called a separator of M if every circuit of M is either contained in S or E-S. Union and intersection of two separators of M is also a separator of M. If0and E are the only separators of M, then M is said to be connected. The minimal non-empty separators of M are called the components of M.
If a circuit of M has only one element, then we call this circuit a loop of M. If a set of two elements{x, y} is a circuit of M, then we call the set{x, y} a pair of parallel elements, x and y are parallel to each other. A matroid is simple if it has no2-circuits and loops. We say that e is a coloop if it is not contained in any circuit of M. A coloop is a component of M.
Let G be a graph. The notation V(G) and E(G) will be used for the vertex-set and edge-set of G, respectively. A path that contains every vertex of G is called a Hamilton path of G; Similarly, a Hamilton cycle of G is a cycle that contains every vertex of G. A graph is hamiltonian if it contains a Hamilton cycle. A graph G is called Hamilton connected if every two vertices of G are connected by a Hamilton path. We now call a graph G positively Hamilton, written G∈H+, if every edge of G is in some Hamilton cycle; G is negatively Hamilton, written G∈H-, if for each edge of G there is a Hamilton cycle avoiding it. When∈G H+and G∈H-, we say that G is uniformly Hamilton. A graph G is also called edge-Hamiltonian if G is positively Hamilton.
The circuit graph of a matroid M is a graph G=G(M) with vertex set V(G) and edge set E(G) such that V(G)=C and E(G)={CC'}C, C'∈C,|C∩C'|≠0), where the same notation is used for the vertices of G and the circuits of M.
Let G be a graph with an orientation D. If an edge e∈E(G) is directed from vertex u to another vertex v, then the tail of e is u, the head of e is v. For each vertex v∈V(G), E+(v) is the set of edges with tail v, and E-(v) is the set of edges with head v. Let Zk denote the abelian group of k elements with identity0. Let F(G, Zk) be the set of all functions from E(G) to Zk. For any given function f∈F(G, Zk), let f is called a Zk-flow in G if (?)f(v)=0for each vertex v∈V(G). The support of f is defined by S(f)={e∈E(G)|f(e)≠0} and f is nowhere- zero if S(f)=E(G) which means that there exists no e E E(G) such that f(e)=0.
If we consider the case that F(G, Z) is the set of all functions from E(G) to Z, where Z denotes the set of integers. For an integer k>2, a nowhere-zero k-flow of G is an orientation D of G together with a function f∈F(G, Z) such that for each e∈E(G),0<|f(e)|
The main content of this thesis is the Hamiltonian cycles in intersection graphs of bases of matroids, vertex disjoint cycles in intersection graphs of bases of matroids and nowhere-zero3-flow in intersection graphs of bases of matroids. The thesis is divided into four chapters.
In Chapter1, a short but relatively complete introduction about graph theory is given. First, we introduce some basic definitions and notations. And then we give a short survey about tree graphs, matroid base graphs and forest graphs. At last, we outline the main results of this thesis. In Chapter2, some properties of the Hamilton cycles in intersection graphs of bases of matroids are given. We discuss the vertex disjoint cycles in intersection graphs of bases of matroids in Chapter3. In Chapter4, we study the nowhere zero3-flows in matroid base graphs.
引文
[1]B. Alspach and G. Liu. Paths and cycles in matroid base graphs. Graphs and Combinatorics,5:207-211,1989.
[2]B. Bollobas. A lower bound for the number of non-isomorphic matroids. Journal of Combinatorial Theory,7:366-368.1969.
[3]B. Bollobas and R. K. Guy. Equitable and proportional coloring of trees. Journal of Combinatorial Theory, Series B,34:177-186,1983.
[4]J. A. Bondy. Transversal matroids, base orderable matroids and graphs. The Quarterly Journal of Mathematics,23:81-89,1972.
[5]J. A. Bondy and A. W. Ingleton. Pancyclic graphs ii. Journal of Combinato-rial Theory, Series B,20:41-46,1976.
[6]J. A. Bondy and U. S. R. Murty. Graph Theory With Applications. American Elsevier, New York,1976.
[7]J. A. Bondy and U. S. R. Murty. Graph Theory. Springer,2008.
[8]H. J. Broersma and X. Li. The connectivity of the basis graph of a branching greedoid. Journal of Graph Theory,16:233-237,1992.
[9]R. A. Brualdi. On foundamental transversal matroids. Proc. Amer. Math. Soc.,45:151-156,1974.
[10]R. A. Brualdi and G. W. Dinolt. Characterization of transversal matroids and their presentations. Journal of Combinatorial Theory, Series B,12:268-286, 1972.
[11]M. Cai. A solution of chartand's problem on spanning trees. Acta Mathemat-icae Applicatae Sinica (English Series),1:97-98,1984.
[12]H. Carpo. Single element extensions of matroids.J. Res. Nat. Bur. Standards Sect. B,69:55-65,1965.
[13]R. L. Cummins. Hamilton circuits in tree graphs. Circuit Theory, IEEE Transactions on.,13:82-90,1966.
[14]R. L. Cummins. Hamiltonian circuits in tree graph. IEEE Trans. Circuits Syst.,13:82-90,1966.
[15]H. Deng and R. Li. The 1-hamiltonian properties of matroid base graphs. Journal of Naturnal Science of Hunan Normal University,22:1-5,1999.
[16]H. Deng and F. Xia. The p3-hamiltonian property of matroid base graphs. Journal of Naturnal Science of Hunan Normal University,1:5-8,2000.
[17]J. Donald, C. Holzmann, and M. Tobey. A characterization of complete matroid base graphs. Journal of Combinatorial Theory, Series B,22:139-158,1977.
[18]J. R. Edmonds. Minimum partition of a matroid into independent subsets. J. Res. Nat. Bur. Standards Sect. B,69:67-72,1965.
[19]J. R. Edmonds. Matroids and the greedy algorithm. Mathematical Program-ming,1:127-136,1971.
[20]G. Fan, H. Lai, R. Xu, C. Q. Zhang, and C. Zhou. Nowhere-zero 3-flows in triangularly connected graphs. Journal of Combin. Theory, Ser B,98:1325-1336,2008.
[21]J. Gao. Quasi-1-hamilton connectedness of tree graphs. Math. Res. and Exposition,7:498,1987.
[22]J. Gao.1-hamilton connectedness of tree graphs. Mathematica Applicata, 2:136-144.1993.
[23]R. K. Guy. Monthly research problems,1969-1975. The American Mathe-matical Monthly,82:995-1004,1975.
[24]F. Harary and M. J. Plantholt. Classification of interpolation theorems for spanning trees and other families of spanning subgraphs. Journal of Graph Theory,13:703-712,1989.
[25]H. Harary, R. J. Mokken, and M. J. Plantholt. Interpolation theorem for diameters of spanning trees. Circuits and Systems, IEEE Transactions on, 30:429-432,1983.
[26]K. Heinrich and G. Liu. A lower bound on the number of spanning trees with k end-vertices. Journal of graph theory,12:95-100,1988.
[27]C. A. Holzman and F. Harary. On the tree graph of a matroid. SIAM Journal on Applied Mathematics,22:187-193,1972.
[28]C. A. Holzmann, P. G. Norton, and M. D. Tobey. A graphical representation of matroids. SIAM Journal on Applied Mathematics,25:618-627,1973.
[29]A. W. Ingleton. Gammoids and transversal matroids. Journal of Combina-torial Theory, Series B,15:51-68,1973.
[30]F. Jaeger. Flows and generalized coloring theorem in graphs. Journal of Combin. Theory, Ser B,26:205-216,1979.
[31]F. Jaeger, N. Linial, and M. Tarsi. Group connectivity of graphs-a nonho-mogeneous analogue of nowhere-zero flow properties, journal=Journal of Combin. Theory, Ser B, year=1992, volume=56, pages=165-182,.
[32]T. Kamae. The existence of a hamilton circuit in a tree graph. Circuit Theory, IEEE Transactions on,14:279-283,1967.
[33]G. Kishi and Y. Kajitani. On hamilton circuits in tree graphs. Circuit Theory, IEEE Transactions on,15:42-50,1968.
[34]G. Kishi and Y. Kajitani. On the realization of tree graphs. Circuit Theory, IEEE Transactions on,15:271-273,1968.
[35]H. Lai. Group connectivity of 3-edge-connected chordal graphs. Graphs and Combin.,16:165-176,2000.
[36]H. Lai. Nowhere-zero 3-flows in locally connected graphs. Journal of Graph Theory,42:211-219,2003.
[37]E. Lawler. Combinatorial Optimization. John Wiley, New York,1972.
[38]L. Li. The hamilton properties of tree graphs. J. Shandong Univ. of Tech-nology,27:261-263,1997.
[39]L. Li, Q. Bian, and G. Liu. The base incidence graph of a matroid. J. Shandong Univ.,40:24-40,2005.
[40]L. Li and G. Liu. The connectivities of the adjacency leaf exchange forest graphs. J. Shandong Univ.,39:49-51,2004.
[41]P. Li. Matroids and Graphs. PhD thesis, Shandong University, Jinan,2005.
[42]P. Li and G. Liu. Cycles in circuit graphs of matroids. Graphs and Combi-natorics,23:425-431,2007.
[43]P. Li and G. Liu. The edge connectivity of circuit graphs of matroid. Com-putational Science-ICCS 2007,4489:440-443,2007.
[44]P. Li and G. Liu. Hamilton cycles in circuit graphs of matroids. Computers and Mathematics with Applications,55:654-659,2008.
[45]X. Li. The connectivities of the see-graph and the aee-graph for the connected spanning k-edge subgraphs of a graph. Discrete Mathematics,183:237-245, 1998.
[46]X. Li, V. Neumann-Lara, and E. Rivera-Campo. Two approaches for the generalization of leaf edge exchange graphs on spanning trees to connected spanning k-edge subgraphs of a graph. Ars Combinatoria,75:257-266,2005.
[47]G. Liu. The connectivities of matroid base graphs. Chinese Journal of Oper-ational Research,3:67-68,1984.
[48]G. Liu. The connectivities of adjacent tree graphs. Acta Mathematicae Ap-plicatae Sinica (English Series),3:313-317,1987.
[49]G. Liu. A lower bound on connectivities of matroid base graphs. Discrete mathematics,64:55-66,1988.
[50]G. Liu. On connectivities of base graph of some matroids. Systems Science and Mathematical Sciences,1:18-21,1988.
[51]G. Liu. The proof of a conjecture on matroid basis graphs. Science in China, 6:593-599,1990.
[52]G. Liu. On connectivities of tree graphs. Journal of graph theory,12:453-459, 2006.
[53]G. Liu and P. Li. Paths in circuit graphs of matroids. Theoretical Computer Science,396:258-263,2008.
[54]G. Liu and L. Zhang. Forest graphs of graphs. Journal of Engineering Math-ematics,22:1100-1104,2005.
[55]L. Lovasz and A. Recski. On the sum of matroids. Acta Mathematica Hun-garica,24:329-333,1973.
[56]S. B. Maurer. Matroid basis graphs i. Journal of Combinatorial Theory, Series B,14:216-240,1973.
[57]S. B. Maurer. Matroid basis graphs ii. Journal of Combinatorial Theory, Series B,15:121-145,1973.
[58]G. J. Minty. On the axiomatic fundations of the theories of directed linear graphs, electrical networks and network programming. J. Math, and Mechan-ics,15:485-520,1966.
[59]U. S. R. Murty. On the number of bases of a matroid. In Proc. Sec-ond Louisiana Conference on Combinatorics, pages 387-410, Louisiana State Univ. Baton Rouge,1971.
[60]D. Naddef and W. R. Pulleyblank. Hamiltonicity and combinatorial polyhe-dra. Journal of Combinatorial Theory, Series B,31:279-312,1981.
[61]J. G. Oxley. Matroid Theory. Oxford University Press, New York,1992.
[62]P. Potocnik, M. Skoviera, and R. Skrekovski. Nowhere-zero 3-flows in abelian cayley graphs. Discrete Mathematics.297:119-127,2005.
[63]R. Rado. A theorem on independence relations. The Quarterly Journal of Mathematics,13:83-89,1942.
[64]P. D. Seymour. Nowhere-zero 6-flows. Journal of Combin. Theory, Ser B, 30:82-94,1981.
[65]H. Shank. A note on hamilton circuits in tree graphs. Circuit Theory, IEEE Transactions on,15:86-86.1968.
[66]J. Shu and C. Q. Zhang. Nowhere-zero 3-flows in products of graphs. Journal of Graph theory,50:79-89,2005.
[67]W. T. Tutte. A contribution on the theory of chromatic polynomial. Canad. Journal of Mathematics,6:217-225,1954.
[68]W. T. Tutte. Matroids and graphs. Transactions of the American Mathemat-ical Society,90:527-552,1959.
[69]W. T. Tutte. An algorithm for determining whether a given binary matroid is graphic. Proceedings of the American Mathematical Society,11:905-917, 1960.
[70]W. T. Tutte. Lectures on matroids. J. Res. Nat. Bur. Standards Sect. B, 69:1-47,1965.
[71]W. T. Tutte. Connectivity in matroids. Canad. J. Math,18:1301-1324,1966.
[72]W. T. Tutte. On the algebraic theory of graph colorings. Journal of Combin. Theory, Ser B,1:15-50,1966.
[73]W. T. Tutte. Introduction to the Theory of Matroids. American Elsevier, 1970.
[74]D. J. A. Welsh. On the hyperplanes of a matroid. Mathematical Proceedings of the Cambridge Philosophical Society,65:11-18,1969.
[75]H. Whitney. On the abstract properties of linear dependence. American Journal of Mathematics,57:509-533,1935.
[76]R. J. Wilson. An introduction to matroid theory. American Mathematical Monthly,80:500-525,1973.
[77]D. R. Woodall. An exchange theorem for bases of matroids. Journal of Combinatorial Theory, Series B,16:227-228,1974.
[78]D. R. Woodall. The induction of matroids by graphs. Journal of the London Mathematical Society,2:27-35,1975.
[79]X. Xu. Some properties of base graphs of matroids. Master's thesis, Shandong University, Jinan,2012.
[80]C. Q. Zhang. Integer Flows and Cycle Covers of Graphs. Marcel Dekker, 1997.
[81]F. Zhang and Z. Chen. Connectivity of (adjacency) tree graphs. J. Xinjiang Univ.,4:1-5,1986.
[82]H. Zheng and G. Liu. Some properties on paths in matroid base graphs. Journal of Systems Science and Complexity,2:104-108,1988.
[2]B. Bollobas. A lower bound for the number of non-isomorphic matroids. Journal of Combinatorial Theory,7:366-368.1969.
[3]B. Bollobas and R. K. Guy. Equitable and proportional coloring of trees. Journal of Combinatorial Theory, Series B,34:177-186,1983.
[4]J. A. Bondy. Transversal matroids, base orderable matroids and graphs. The Quarterly Journal of Mathematics,23:81-89,1972.
[5]J. A. Bondy and A. W. Ingleton. Pancyclic graphs ii. Journal of Combinato-rial Theory, Series B,20:41-46,1976.
[6]J. A. Bondy and U. S. R. Murty. Graph Theory With Applications. American Elsevier, New York,1976.
[7]J. A. Bondy and U. S. R. Murty. Graph Theory. Springer,2008.
[8]H. J. Broersma and X. Li. The connectivity of the basis graph of a branching greedoid. Journal of Graph Theory,16:233-237,1992.
[9]R. A. Brualdi. On foundamental transversal matroids. Proc. Amer. Math. Soc.,45:151-156,1974.
[10]R. A. Brualdi and G. W. Dinolt. Characterization of transversal matroids and their presentations. Journal of Combinatorial Theory, Series B,12:268-286, 1972.
[11]M. Cai. A solution of chartand's problem on spanning trees. Acta Mathemat-icae Applicatae Sinica (English Series),1:97-98,1984.
[12]H. Carpo. Single element extensions of matroids.J. Res. Nat. Bur. Standards Sect. B,69:55-65,1965.
[13]R. L. Cummins. Hamilton circuits in tree graphs. Circuit Theory, IEEE Transactions on.,13:82-90,1966.
[14]R. L. Cummins. Hamiltonian circuits in tree graph. IEEE Trans. Circuits Syst.,13:82-90,1966.
[15]H. Deng and R. Li. The 1-hamiltonian properties of matroid base graphs. Journal of Naturnal Science of Hunan Normal University,22:1-5,1999.
[16]H. Deng and F. Xia. The p3-hamiltonian property of matroid base graphs. Journal of Naturnal Science of Hunan Normal University,1:5-8,2000.
[17]J. Donald, C. Holzmann, and M. Tobey. A characterization of complete matroid base graphs. Journal of Combinatorial Theory, Series B,22:139-158,1977.
[18]J. R. Edmonds. Minimum partition of a matroid into independent subsets. J. Res. Nat. Bur. Standards Sect. B,69:67-72,1965.
[19]J. R. Edmonds. Matroids and the greedy algorithm. Mathematical Program-ming,1:127-136,1971.
[20]G. Fan, H. Lai, R. Xu, C. Q. Zhang, and C. Zhou. Nowhere-zero 3-flows in triangularly connected graphs. Journal of Combin. Theory, Ser B,98:1325-1336,2008.
[21]J. Gao. Quasi-1-hamilton connectedness of tree graphs. Math. Res. and Exposition,7:498,1987.
[22]J. Gao.1-hamilton connectedness of tree graphs. Mathematica Applicata, 2:136-144.1993.
[23]R. K. Guy. Monthly research problems,1969-1975. The American Mathe-matical Monthly,82:995-1004,1975.
[24]F. Harary and M. J. Plantholt. Classification of interpolation theorems for spanning trees and other families of spanning subgraphs. Journal of Graph Theory,13:703-712,1989.
[25]H. Harary, R. J. Mokken, and M. J. Plantholt. Interpolation theorem for diameters of spanning trees. Circuits and Systems, IEEE Transactions on, 30:429-432,1983.
[26]K. Heinrich and G. Liu. A lower bound on the number of spanning trees with k end-vertices. Journal of graph theory,12:95-100,1988.
[27]C. A. Holzman and F. Harary. On the tree graph of a matroid. SIAM Journal on Applied Mathematics,22:187-193,1972.
[28]C. A. Holzmann, P. G. Norton, and M. D. Tobey. A graphical representation of matroids. SIAM Journal on Applied Mathematics,25:618-627,1973.
[29]A. W. Ingleton. Gammoids and transversal matroids. Journal of Combina-torial Theory, Series B,15:51-68,1973.
[30]F. Jaeger. Flows and generalized coloring theorem in graphs. Journal of Combin. Theory, Ser B,26:205-216,1979.
[31]F. Jaeger, N. Linial, and M. Tarsi. Group connectivity of graphs-a nonho-mogeneous analogue of nowhere-zero flow properties, journal=Journal of Combin. Theory, Ser B, year=1992, volume=56, pages=165-182,.
[32]T. Kamae. The existence of a hamilton circuit in a tree graph. Circuit Theory, IEEE Transactions on,14:279-283,1967.
[33]G. Kishi and Y. Kajitani. On hamilton circuits in tree graphs. Circuit Theory, IEEE Transactions on,15:42-50,1968.
[34]G. Kishi and Y. Kajitani. On the realization of tree graphs. Circuit Theory, IEEE Transactions on,15:271-273,1968.
[35]H. Lai. Group connectivity of 3-edge-connected chordal graphs. Graphs and Combin.,16:165-176,2000.
[36]H. Lai. Nowhere-zero 3-flows in locally connected graphs. Journal of Graph Theory,42:211-219,2003.
[37]E. Lawler. Combinatorial Optimization. John Wiley, New York,1972.
[38]L. Li. The hamilton properties of tree graphs. J. Shandong Univ. of Tech-nology,27:261-263,1997.
[39]L. Li, Q. Bian, and G. Liu. The base incidence graph of a matroid. J. Shandong Univ.,40:24-40,2005.
[40]L. Li and G. Liu. The connectivities of the adjacency leaf exchange forest graphs. J. Shandong Univ.,39:49-51,2004.
[41]P. Li. Matroids and Graphs. PhD thesis, Shandong University, Jinan,2005.
[42]P. Li and G. Liu. Cycles in circuit graphs of matroids. Graphs and Combi-natorics,23:425-431,2007.
[43]P. Li and G. Liu. The edge connectivity of circuit graphs of matroid. Com-putational Science-ICCS 2007,4489:440-443,2007.
[44]P. Li and G. Liu. Hamilton cycles in circuit graphs of matroids. Computers and Mathematics with Applications,55:654-659,2008.
[45]X. Li. The connectivities of the see-graph and the aee-graph for the connected spanning k-edge subgraphs of a graph. Discrete Mathematics,183:237-245, 1998.
[46]X. Li, V. Neumann-Lara, and E. Rivera-Campo. Two approaches for the generalization of leaf edge exchange graphs on spanning trees to connected spanning k-edge subgraphs of a graph. Ars Combinatoria,75:257-266,2005.
[47]G. Liu. The connectivities of matroid base graphs. Chinese Journal of Oper-ational Research,3:67-68,1984.
[48]G. Liu. The connectivities of adjacent tree graphs. Acta Mathematicae Ap-plicatae Sinica (English Series),3:313-317,1987.
[49]G. Liu. A lower bound on connectivities of matroid base graphs. Discrete mathematics,64:55-66,1988.
[50]G. Liu. On connectivities of base graph of some matroids. Systems Science and Mathematical Sciences,1:18-21,1988.
[51]G. Liu. The proof of a conjecture on matroid basis graphs. Science in China, 6:593-599,1990.
[52]G. Liu. On connectivities of tree graphs. Journal of graph theory,12:453-459, 2006.
[53]G. Liu and P. Li. Paths in circuit graphs of matroids. Theoretical Computer Science,396:258-263,2008.
[54]G. Liu and L. Zhang. Forest graphs of graphs. Journal of Engineering Math-ematics,22:1100-1104,2005.
[55]L. Lovasz and A. Recski. On the sum of matroids. Acta Mathematica Hun-garica,24:329-333,1973.
[56]S. B. Maurer. Matroid basis graphs i. Journal of Combinatorial Theory, Series B,14:216-240,1973.
[57]S. B. Maurer. Matroid basis graphs ii. Journal of Combinatorial Theory, Series B,15:121-145,1973.
[58]G. J. Minty. On the axiomatic fundations of the theories of directed linear graphs, electrical networks and network programming. J. Math, and Mechan-ics,15:485-520,1966.
[59]U. S. R. Murty. On the number of bases of a matroid. In Proc. Sec-ond Louisiana Conference on Combinatorics, pages 387-410, Louisiana State Univ. Baton Rouge,1971.
[60]D. Naddef and W. R. Pulleyblank. Hamiltonicity and combinatorial polyhe-dra. Journal of Combinatorial Theory, Series B,31:279-312,1981.
[61]J. G. Oxley. Matroid Theory. Oxford University Press, New York,1992.
[62]P. Potocnik, M. Skoviera, and R. Skrekovski. Nowhere-zero 3-flows in abelian cayley graphs. Discrete Mathematics.297:119-127,2005.
[63]R. Rado. A theorem on independence relations. The Quarterly Journal of Mathematics,13:83-89,1942.
[64]P. D. Seymour. Nowhere-zero 6-flows. Journal of Combin. Theory, Ser B, 30:82-94,1981.
[65]H. Shank. A note on hamilton circuits in tree graphs. Circuit Theory, IEEE Transactions on,15:86-86.1968.
[66]J. Shu and C. Q. Zhang. Nowhere-zero 3-flows in products of graphs. Journal of Graph theory,50:79-89,2005.
[67]W. T. Tutte. A contribution on the theory of chromatic polynomial. Canad. Journal of Mathematics,6:217-225,1954.
[68]W. T. Tutte. Matroids and graphs. Transactions of the American Mathemat-ical Society,90:527-552,1959.
[69]W. T. Tutte. An algorithm for determining whether a given binary matroid is graphic. Proceedings of the American Mathematical Society,11:905-917, 1960.
[70]W. T. Tutte. Lectures on matroids. J. Res. Nat. Bur. Standards Sect. B, 69:1-47,1965.
[71]W. T. Tutte. Connectivity in matroids. Canad. J. Math,18:1301-1324,1966.
[72]W. T. Tutte. On the algebraic theory of graph colorings. Journal of Combin. Theory, Ser B,1:15-50,1966.
[73]W. T. Tutte. Introduction to the Theory of Matroids. American Elsevier, 1970.
[74]D. J. A. Welsh. On the hyperplanes of a matroid. Mathematical Proceedings of the Cambridge Philosophical Society,65:11-18,1969.
[75]H. Whitney. On the abstract properties of linear dependence. American Journal of Mathematics,57:509-533,1935.
[76]R. J. Wilson. An introduction to matroid theory. American Mathematical Monthly,80:500-525,1973.
[77]D. R. Woodall. An exchange theorem for bases of matroids. Journal of Combinatorial Theory, Series B,16:227-228,1974.
[78]D. R. Woodall. The induction of matroids by graphs. Journal of the London Mathematical Society,2:27-35,1975.
[79]X. Xu. Some properties of base graphs of matroids. Master's thesis, Shandong University, Jinan,2012.
[80]C. Q. Zhang. Integer Flows and Cycle Covers of Graphs. Marcel Dekker, 1997.
[81]F. Zhang and Z. Chen. Connectivity of (adjacency) tree graphs. J. Xinjiang Univ.,4:1-5,1986.
[82]H. Zheng and G. Liu. Some properties on paths in matroid base graphs. Journal of Systems Science and Complexity,2:104-108,1988.