拟阵圈图的一些性质
|
摘要
图论和拟阵理论在二十世纪经历了空前的发展.图的支撑树及拟阵的基都是组合理论的基本研究对象.一个连通图的树图能够反映该图的不同支撑树之间的变换关系.因此,研究一个图的树图有助于我们更好地了解该图的性质.同样的一个拟阵的基图能够反映该拟阵的不同基之间的变换关系.因此,研究一个拟阵的基图有助于我们更好地了解该拟阵的性质.近些年来,树图和拟阵的基图被推广得到了一些新的图.为了研究拟阵中圈图的性质,我们提出了拟阵圈图的概念,并且研究了圈图的连通度,圈图中圈的性质,路的性质,并且把圈图的概念推广为n阶圈图,并得到了n阶圈图的一些性质。
设E是一个有限集.如果S1,S2(?)E,那么S1-S2={χ(?)χ∈S1和x(?)S2}.
一个拟阵M就是一个有限集E以及E的一个非空子集族(?),且满足以下条件：
(C1)若C1,C2∈(?)且C1(?)C2,则C1=C2.
(C2)设C1,C2∈(?)并且a,b∈E.若a∈C1∩C2且b∈C1-C2,则存在C3∈(?)满足b∈C3(?)(C1∪C2)-{a}.
当C∈(?)(M),我们称C为M的一个圈.如果M的一个圈只有一个元素,则称之为M的一个环.如果两个元素的集合{x,y}是M的一个圈,则称{x,y}为一对平行元.如果M既没有环也没有平行元,则称M是一个简单拟阵.如果一个元素含在M的任一基中,则称之为M的一个反环.
如果S是E的一个子集,且对任意的圈C,都有C(?)S或者C(?)E＼S.则称S为M的一个分离集.显然E和(?)都是M的分离集.M的极小分离集称为M一个分支.如果拟阵M只有一个分支,则称M为连通拟阵.设e∈E,则M·e和M△e分别表示由拟阵M经过收缩和删除e后所得到的拟阵.
拟阵M=(E,(?))的基图是这样一个图G,其中V(G)=(?),E(G)={B1B2：B1,B2∈(?),且|B1＼B2|=1},这里图G的顶点和M的基用同样的符号表示.
设G是一个图,图G的点集和边集分别记为V(G)和E(G),令v(G)=|V(G)|.包含G的每个点的路称为G一条哈密顿路；同样地,包含G的每个点的圈称为G一个哈密顿圈.如果个图存在一个哈密顿圈,则称之为哈密顿的.如果对一个图G的任意两个顶点来说,G都有一条哈密顿路连接它们.则称G是哈密顿连通的.如果对一个图G的任意一条边来说,G都有一个含这条边的哈密顿圈,则称G是边哈密顿的,或者称G是正哈密顿的,记为G∈H+.如果对一个图G的任意一条边来说,G都有一个不包含这条边的哈密顿圈,则称G是负哈密顿的,记为G∈H-.如果G既是正哈密顿的,又是负哈密顿的,我们称G是一致哈密顿的。
一个有n个顶点的图G称为顶点泛圈的,当且仅当对任意的k,3≤k≤n,以及G的任意一个顶点,G都存在一个过该顶点的长度为k的圈.一个有n个顶点的图G称为边泛圈的,当且仅当对任意的k,3≤k≤n,以及G的任意一条边,G都存在一个长度为k的圈包含这条边.
现在我们给出拟阵圈图的概念.定义拟阵M的圈图G=G(M)的顶点集V(G)=(?),边集E(G)={CC′|C，C′∈(?),|C∩C′|≠0}。这里C和C′既代表G的顶点,也代表M的圈.
定义拟阵M的k阶圈图Ck(M)的顶点集为V(Ck(M))=(?)(M).两个顶点C,C′∈(?)(M)在Ck(M)中相邻当且仅当在M中|C∩C′|≥k.为了符号表示方便,我们既用C表示Ck(M)的顶点,也用C表示M中的圈.
本文分为五章.第一章给出关于树图,拟阵基图以及森林图的一个简短但相对完整的综述.第二章给出拟阵圈图的概念,并讨论拟阵圈图的连通度和边连通度.第三章我们深入讨论了拟阵圈图的哈密顿性,边泛圈性以及圈图中顶点不交圈的性质.第四章讨论了拟阵圈图中路的性质.第五章我们给出了拟阵的圈图的定义,并讨论了它的直径和连通度.
下面列出本文的主要结果.
结论1设G=G(M)是一个连通拟阵M的圈图,而且B是M的一个基,则G的连通度k(G)≥2|E-B|-2.
结论2设G=G(M)是一个连通拟阵M的圈图,而且G的最小度是δ(G),则δ(G)≥2|E-B|-2.
结论3设G=G(M)是一个连通拟阵M的圈图,而且G的最小度是δ(G),则G的边连通度k′(G)=δ(G).
结论4设G=G(M)是一个连通拟阵M的圈图,而且M含有至少三个圈,则G=G(M)是边泛圈的.
结论5设G=G(M)是一个连通拟阵M的圈图,而且M含有至少四个圈,则G是一致哈密顿的.
结论6设G=G(M)是一个连通拟阵M的圈图,如果|V(G)|=n并且k1+k2+…+kp=n(ki为整数,ki≥3,i=1,2,…,p),则G有一个2-因子F包含p个顶点不交的圈D1,D2,…,Dp而且圈Di的长度为ki(i=1,2,…,p).
结论7设G=G(M)是一个连通拟阵M的圈图,而且M含有至少三个圈,则G的直径不超过2.并且,d(G(M))=2当且仅当M中有两个没有公共元素的圈.
结论8设G=G(M)是一个连通拟阵M的圈图,如果|V(G)|=n并且C1,C2∈V(G),则对于任意的k满足2≤k≤n-1,存在一条长度为k的路连接C1和C2.
结论9设M是一个连通简单拟阵.则如下结论成立.(ⅰ)C2(M)是连通的.(ⅱ)如果M没有一个约束子拟阵同构于U2,6,则在C2(M)中任何两个不相邻的顶点C1和C2有一个公共邻点C3.(ⅲ)C2(M)的直径不超过2当且仅当对于任何边集合X(?)E,M在X上的约束子拟阵都不同构于U2,6.
结论10设M是一个包含至少两个圈的连通简单拟阵,且M不是一条线,则C2(M)是2-连通的.
Matroid theory dates from the 1930's and Whitney in his basic paper [69] con-ceived a matroid as an abstract generalization of a matrix. Matroid theory gives us powerful techniques for understanding combinatorial optimization problems and for de-signing polynomial-time algorithms. Graph theory and matroid theory have witnessed an unprecedented growth in the twentieth century. 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 studing 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 relationship of different bases, so studing 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, we give a new definition as circuit graph of matroid, and give some properties of this graph.
Let E be a finite set of elements.For S1,S2,S2 (?) E, set S1-S2={x(?)x∈S1andx (?) S2}. Let(?) be a collection of non-null subsets of E which satisfies the following two axioms:
(C1) A proper subset of a member of(?) is not a member of (?).
(C2) If a∈C1 n C2 and b∈C1-C2 where C1,C2∈(?) and a,b∈E, then there exists a C3∈V such that b∈C3 c (C1 (?) C2)-{α}.
Then M= (E, (?)) is called a matroid on E. We refer to the members of(?) as circuits of matroid M. The family of circuits of M determines a matroid.
A subset of E that does not contain any circuit is called an independent set of M. A maximal independent set is called a basis of M, denoted by B(M). Let(?)(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' in B'such that B∪{b'}-{b} is also a basis.
Let M=(E,(?)) be a matroid. If X (?) E, then the matroid on E-X whose circuits are those of M which are contained in E-X is called the restriction of M to E-X (or the matroid obtained by deleting X from M) and is denoted by M\X or M(?)(E-X).
There is another derived matroid of importance. If X (?) E, then the family of minimal non-empty intersections of E-X with circuits of M is the family of circuits of a matroid on E-X called the contraction of M to E-X (or the matroid obtained by contracting X out of M) and is denoted by M/X.
If X={e}, we use M\e and M/e to denote the matroid obtained from M by delet-ing and contracting e, respectively. A matroid obtained from M by limited times of contractions and limited times of deletions is called a minor matroid of M.
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. Ifφand 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 no 2-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 M be a matroid and let (?) denote the family of bases of M. Let (?) denote the family of complements of members of (?) in E. Then (?) is the family of bases of a matroid, denoted by M*, called the dual of M. The circuits of M* are called the co-circuits of M.(?)(M\e)={B(?)B(?)B∈(?)M), e(?)B} and (?)(M/e)={B-{e}(?)B∈(?)(M), e∈B}.
A walk in a graph G is an alternating sequence of vertices and edges such that ei is an edge joining vi and vi+1. For simplicity, P=ν0ν1…νκ+1will be written thereby implying the occurrences of the edges. If Q=νκ+1νκ+2…νn is a walk, then If P=ν0,e0,ν1, e1,…,νκ,eκ,νκ+1,is a walk in which all the vertices are distinct, then P is called a path. Ifν0,ν1,…,νκ+1 are distinct andν0=νκ+1, then P is called a cycle. The length of a walk is the number of edges contained in the sequence.
A family of paths in G is said to be internally-disjoint if no vertex of G is an internal vertex of more than one path of the family.
A vertex cut of G is a subsetν' ofνsuch that G-ν' is disconnected. Aκ-vertex cut is a vertex cut of k elements. The only graphs which do not have vertex cuts are those that contain complete graphs as spanning subgraphs. If G has at least one pair of distinct nonadjacent vertices, the connectivityκ(G) of G is the minimum k for which G has a k-vertex cut; otherwise, we defineκ(G) to be(?)ν(G)(?)-1. We call a graph with just one vertex trivial and all other graphs nontrivial. Thusκ(G)=0 if G is either trivial or disconnected. G is said to beκ-connected ifκ(G)≥κ. All nontrivial connected graphs are 1-connected.
For subsets S and S'of V(G), we denote by [S,S'] the set of edges with one end in S and the other in S'. An edge cut of G is a subset of E(G) of the form [S,S], where S is a nonempty proper subset of V(G) and (?)= V\S. Aκ-edge cut is an edge cut of k elements. If G is nontrivial and E' is an edge cut of G, then G-E'is disconnected. We then define the edge connectivityκ'(G) of G to be the minimum k for which G has aκ-edge cut. G is said to beκ-edge-connected ifκ'(G)≥k.
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.
A graph G with n vertices is called vertex-pancyclic if for any integer k,3≤k≤n, and any vertex of G, the vertex lies in a cycle of length k. A graph G with n vertices is called edge-pancyclic if for any integer k,3≤k≤n, and any edge of G, there is a cycle of length k containing the edge. W5 is a wheel on 5 vertices.
Now we give a new concept as follows. 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)=(?) and E(G)={CC'| C, C'∈(?),|C∩C'|≠0}, where the same notation is used for the vertices of G and the circuits of M.
The kth order circuit graph Ck(M) of M has vertex set V(Cκ(M))=(?)(M), the set of all circuits of M. Two vertices C, C'∈(?)(M) are adjacent in Cκ(M) if and only if (?)C∩C'(?) k. For notational convenience, for a circuit C∈(?)(M), we shall use C to denote both a vertex in Cκ(M) and a circuit (also as a subset of E(M)) of M.
The thesis is divided into six chapters. A short but relatively complete survey about tree graphs, matroid base graphs and forest graphs is given in Chapter 1. We discuss the connectivities of matroid circuit graphs in Chapter 2. In Chapter 3, some properties of the cycles in circuit graphs of matroids are given. Paths in matroid circuit graphs are studied in Chapter 4. In Chapter 5, we give a new concept as kth order circuit graph of a matroid M, and studied its connectivities and diameter.
In the following, we will list our main results in this thesis.
Conclusion 1. Suppose that G=G(M) is the circuit graph of a connected matroid M. Then the connectivityκ(G)≥2(?)E-B(?)-2, where B is a base of M..
Conclusion 2. Suppose that G=G(M) is the circuit graph of a connected matroid M with minimum degreeδ(G). Thenδ(G)≥2(?)E-B(?)-2.
Conclusion 3. Suppose that G=G(M) is the circuit graph of a connected matroid M with minimum degreeδ(G). Then the edge connectivityκ'(G)=κ(G).
Conclusion 4. For any connected matroid M=(E, I) which has at least three circuits, the circuit graph G=G(M) is edge-pancyclic.
Conclusion 5. For any connected matroid M, the circuit graph G(M) is uniformly Hamilton whenever G(M) contains at least four vertices.
Conclusion 6. Let G be the circuit graph of a connected matroid M=(E, I). If (?)V(G)(?)= n andκ1+κ2+…κp= n where ki is an integer and ki≥3, i=1,2,…,p, then G has a 2-factor F containing p vertex-disjoint cycles D1,D2,…, Dp such that the length of Di is ki(i= 1,2,…, p).
Conclusion 7. Let M=(E,(?)) be a connected matroid with at least three circuits. If G=G(M) is the circuit graph of M, then the diameter of G is at most 2. Furthermore, d(G(M))=2 if and only if there exist two circuits such that they have no element in common.
Conclusion 8. Let G=G(M) be the circuit graph of a connected matroid M=(E,(?)). If|V(G)|= n and C1,C2∈V(G), then there is a path of length k joining C1and C2 for any k satisfying 2≤κ≤n-1.
Conclusion 9. Let M be a connected simple matroid. Each of the following holds. (i) C2(M) is connected. (ii) If M has no restriction isomorphic to U2.6, then every pair of nonadjacent vertices C1 and C2 in C2(M) has a common neighbor C3. (iii)The diameter of C2(M) is at most two if and only if for any X (?) E, the restriction of M to X is not isomorphic to U2,6.
Conclusion 10. Let M be a connected simple matroid with more than one circuit, but M is not a line, then C2(M) is 2-connected.
设E是一个有限集.如果S1,S2(?)E,那么S1-S2={χ(?)χ∈S1和x(?)S2}.
一个拟阵M就是一个有限集E以及E的一个非空子集族(?),且满足以下条件：
(C1)若C1,C2∈(?)且C1(?)C2,则C1=C2.
(C2)设C1,C2∈(?)并且a,b∈E.若a∈C1∩C2且b∈C1-C2,则存在C3∈(?)满足b∈C3(?)(C1∪C2)-{a}.
当C∈(?)(M),我们称C为M的一个圈.如果M的一个圈只有一个元素,则称之为M的一个环.如果两个元素的集合{x,y}是M的一个圈,则称{x,y}为一对平行元.如果M既没有环也没有平行元,则称M是一个简单拟阵.如果一个元素含在M的任一基中,则称之为M的一个反环.
如果S是E的一个子集,且对任意的圈C,都有C(?)S或者C(?)E＼S.则称S为M的一个分离集.显然E和(?)都是M的分离集.M的极小分离集称为M一个分支.如果拟阵M只有一个分支,则称M为连通拟阵.设e∈E,则M·e和M△e分别表示由拟阵M经过收缩和删除e后所得到的拟阵.
拟阵M=(E,(?))的基图是这样一个图G,其中V(G)=(?),E(G)={B1B2：B1,B2∈(?),且|B1＼B2|=1},这里图G的顶点和M的基用同样的符号表示.
设G是一个图,图G的点集和边集分别记为V(G)和E(G),令v(G)=|V(G)|.包含G的每个点的路称为G一条哈密顿路；同样地,包含G的每个点的圈称为G一个哈密顿圈.如果个图存在一个哈密顿圈,则称之为哈密顿的.如果对一个图G的任意两个顶点来说,G都有一条哈密顿路连接它们.则称G是哈密顿连通的.如果对一个图G的任意一条边来说,G都有一个含这条边的哈密顿圈,则称G是边哈密顿的,或者称G是正哈密顿的,记为G∈H+.如果对一个图G的任意一条边来说,G都有一个不包含这条边的哈密顿圈,则称G是负哈密顿的,记为G∈H-.如果G既是正哈密顿的,又是负哈密顿的,我们称G是一致哈密顿的。
一个有n个顶点的图G称为顶点泛圈的,当且仅当对任意的k,3≤k≤n,以及G的任意一个顶点,G都存在一个过该顶点的长度为k的圈.一个有n个顶点的图G称为边泛圈的,当且仅当对任意的k,3≤k≤n,以及G的任意一条边,G都存在一个长度为k的圈包含这条边.
现在我们给出拟阵圈图的概念.定义拟阵M的圈图G=G(M)的顶点集V(G)=(?),边集E(G)={CC′|C，C′∈(?),|C∩C′|≠0}。这里C和C′既代表G的顶点,也代表M的圈.
定义拟阵M的k阶圈图Ck(M)的顶点集为V(Ck(M))=(?)(M).两个顶点C,C′∈(?)(M)在Ck(M)中相邻当且仅当在M中|C∩C′|≥k.为了符号表示方便,我们既用C表示Ck(M)的顶点,也用C表示M中的圈.
本文分为五章.第一章给出关于树图,拟阵基图以及森林图的一个简短但相对完整的综述.第二章给出拟阵圈图的概念,并讨论拟阵圈图的连通度和边连通度.第三章我们深入讨论了拟阵圈图的哈密顿性,边泛圈性以及圈图中顶点不交圈的性质.第四章讨论了拟阵圈图中路的性质.第五章我们给出了拟阵的圈图的定义,并讨论了它的直径和连通度.
下面列出本文的主要结果.
结论1设G=G(M)是一个连通拟阵M的圈图,而且B是M的一个基,则G的连通度k(G)≥2|E-B|-2.
结论2设G=G(M)是一个连通拟阵M的圈图,而且G的最小度是δ(G),则δ(G)≥2|E-B|-2.
结论3设G=G(M)是一个连通拟阵M的圈图,而且G的最小度是δ(G),则G的边连通度k′(G)=δ(G).
结论4设G=G(M)是一个连通拟阵M的圈图,而且M含有至少三个圈,则G=G(M)是边泛圈的.
结论5设G=G(M)是一个连通拟阵M的圈图,而且M含有至少四个圈,则G是一致哈密顿的.
结论6设G=G(M)是一个连通拟阵M的圈图,如果|V(G)|=n并且k1+k2+…+kp=n(ki为整数,ki≥3,i=1,2,…,p),则G有一个2-因子F包含p个顶点不交的圈D1,D2,…,Dp而且圈Di的长度为ki(i=1,2,…,p).
结论7设G=G(M)是一个连通拟阵M的圈图,而且M含有至少三个圈,则G的直径不超过2.并且,d(G(M))=2当且仅当M中有两个没有公共元素的圈.
结论8设G=G(M)是一个连通拟阵M的圈图,如果|V(G)|=n并且C1,C2∈V(G),则对于任意的k满足2≤k≤n-1,存在一条长度为k的路连接C1和C2.
结论9设M是一个连通简单拟阵.则如下结论成立.(ⅰ)C2(M)是连通的.(ⅱ)如果M没有一个约束子拟阵同构于U2,6,则在C2(M)中任何两个不相邻的顶点C1和C2有一个公共邻点C3.(ⅲ)C2(M)的直径不超过2当且仅当对于任何边集合X(?)E,M在X上的约束子拟阵都不同构于U2,6.
结论10设M是一个包含至少两个圈的连通简单拟阵,且M不是一条线,则C2(M)是2-连通的.
Matroid theory dates from the 1930's and Whitney in his basic paper [69] con-ceived a matroid as an abstract generalization of a matrix. Matroid theory gives us powerful techniques for understanding combinatorial optimization problems and for de-signing polynomial-time algorithms. Graph theory and matroid theory have witnessed an unprecedented growth in the twentieth century. 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 studing 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 relationship of different bases, so studing 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, we give a new definition as circuit graph of matroid, and give some properties of this graph.
Let E be a finite set of elements.For S1,S2,S2 (?) E, set S1-S2={x(?)x∈S1andx (?) S2}. Let(?) be a collection of non-null subsets of E which satisfies the following two axioms:
(C1) A proper subset of a member of(?) is not a member of (?).
(C2) If a∈C1 n C2 and b∈C1-C2 where C1,C2∈(?) and a,b∈E, then there exists a C3∈V such that b∈C3 c (C1 (?) C2)-{α}.
Then M= (E, (?)) is called a matroid on E. We refer to the members of(?) as circuits of matroid M. The family of circuits of M determines a matroid.
A subset of E that does not contain any circuit is called an independent set of M. A maximal independent set is called a basis of M, denoted by B(M). Let(?)(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' in B'such that B∪{b'}-{b} is also a basis.
Let M=(E,(?)) be a matroid. If X (?) E, then the matroid on E-X whose circuits are those of M which are contained in E-X is called the restriction of M to E-X (or the matroid obtained by deleting X from M) and is denoted by M\X or M(?)(E-X).
There is another derived matroid of importance. If X (?) E, then the family of minimal non-empty intersections of E-X with circuits of M is the family of circuits of a matroid on E-X called the contraction of M to E-X (or the matroid obtained by contracting X out of M) and is denoted by M/X.
If X={e}, we use M\e and M/e to denote the matroid obtained from M by delet-ing and contracting e, respectively. A matroid obtained from M by limited times of contractions and limited times of deletions is called a minor matroid of M.
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. Ifφand 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 no 2-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 M be a matroid and let (?) denote the family of bases of M. Let (?) denote the family of complements of members of (?) in E. Then (?) is the family of bases of a matroid, denoted by M*, called the dual of M. The circuits of M* are called the co-circuits of M.(?)(M\e)={B(?)B(?)B∈(?)M), e(?)B} and (?)(M/e)={B-{e}(?)B∈(?)(M), e∈B}.
A walk in a graph G is an alternating sequence of vertices and edges such that ei is an edge joining vi and vi+1. For simplicity, P=ν0ν1…νκ+1will be written thereby implying the occurrences of the edges. If Q=νκ+1νκ+2…νn is a walk, then If P=ν0,e0,ν1, e1,…,νκ,eκ,νκ+1,is a walk in which all the vertices are distinct, then P is called a path. Ifν0,ν1,…,νκ+1 are distinct andν0=νκ+1, then P is called a cycle. The length of a walk is the number of edges contained in the sequence.
A family of paths in G is said to be internally-disjoint if no vertex of G is an internal vertex of more than one path of the family.
A vertex cut of G is a subsetν' ofνsuch that G-ν' is disconnected. Aκ-vertex cut is a vertex cut of k elements. The only graphs which do not have vertex cuts are those that contain complete graphs as spanning subgraphs. If G has at least one pair of distinct nonadjacent vertices, the connectivityκ(G) of G is the minimum k for which G has a k-vertex cut; otherwise, we defineκ(G) to be(?)ν(G)(?)-1. We call a graph with just one vertex trivial and all other graphs nontrivial. Thusκ(G)=0 if G is either trivial or disconnected. G is said to beκ-connected ifκ(G)≥κ. All nontrivial connected graphs are 1-connected.
For subsets S and S'of V(G), we denote by [S,S'] the set of edges with one end in S and the other in S'. An edge cut of G is a subset of E(G) of the form [S,S], where S is a nonempty proper subset of V(G) and (?)= V\S. Aκ-edge cut is an edge cut of k elements. If G is nontrivial and E' is an edge cut of G, then G-E'is disconnected. We then define the edge connectivityκ'(G) of G to be the minimum k for which G has aκ-edge cut. G is said to beκ-edge-connected ifκ'(G)≥k.
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.
A graph G with n vertices is called vertex-pancyclic if for any integer k,3≤k≤n, and any vertex of G, the vertex lies in a cycle of length k. A graph G with n vertices is called edge-pancyclic if for any integer k,3≤k≤n, and any edge of G, there is a cycle of length k containing the edge. W5 is a wheel on 5 vertices.
Now we give a new concept as follows. 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)=(?) and E(G)={CC'| C, C'∈(?),|C∩C'|≠0}, where the same notation is used for the vertices of G and the circuits of M.
The kth order circuit graph Ck(M) of M has vertex set V(Cκ(M))=(?)(M), the set of all circuits of M. Two vertices C, C'∈(?)(M) are adjacent in Cκ(M) if and only if (?)C∩C'(?) k. For notational convenience, for a circuit C∈(?)(M), we shall use C to denote both a vertex in Cκ(M) and a circuit (also as a subset of E(M)) of M.
The thesis is divided into six chapters. A short but relatively complete survey about tree graphs, matroid base graphs and forest graphs is given in Chapter 1. We discuss the connectivities of matroid circuit graphs in Chapter 2. In Chapter 3, some properties of the cycles in circuit graphs of matroids are given. Paths in matroid circuit graphs are studied in Chapter 4. In Chapter 5, we give a new concept as kth order circuit graph of a matroid M, and studied its connectivities and diameter.
In the following, we will list our main results in this thesis.
Conclusion 1. Suppose that G=G(M) is the circuit graph of a connected matroid M. Then the connectivityκ(G)≥2(?)E-B(?)-2, where B is a base of M..
Conclusion 2. Suppose that G=G(M) is the circuit graph of a connected matroid M with minimum degreeδ(G). Thenδ(G)≥2(?)E-B(?)-2.
Conclusion 3. Suppose that G=G(M) is the circuit graph of a connected matroid M with minimum degreeδ(G). Then the edge connectivityκ'(G)=κ(G).
Conclusion 4. For any connected matroid M=(E, I) which has at least three circuits, the circuit graph G=G(M) is edge-pancyclic.
Conclusion 5. For any connected matroid M, the circuit graph G(M) is uniformly Hamilton whenever G(M) contains at least four vertices.
Conclusion 6. Let G be the circuit graph of a connected matroid M=(E, I). If (?)V(G)(?)= n andκ1+κ2+…κp= n where ki is an integer and ki≥3, i=1,2,…,p, then G has a 2-factor F containing p vertex-disjoint cycles D1,D2,…, Dp such that the length of Di is ki(i= 1,2,…, p).
Conclusion 7. Let M=(E,(?)) be a connected matroid with at least three circuits. If G=G(M) is the circuit graph of M, then the diameter of G is at most 2. Furthermore, d(G(M))=2 if and only if there exist two circuits such that they have no element in common.
Conclusion 8. Let G=G(M) be the circuit graph of a connected matroid M=(E,(?)). If|V(G)|= n and C1,C2∈V(G), then there is a path of length k joining C1and C2 for any k satisfying 2≤κ≤n-1.
Conclusion 9. Let M be a connected simple matroid. Each of the following holds. (i) C2(M) is connected. (ii) If M has no restriction isomorphic to U2.6, then every pair of nonadjacent vertices C1 and C2 in C2(M) has a common neighbor C3. (iii)The diameter of C2(M) is at most two if and only if for any X (?) E, the restriction of M to X is not isomorphic to U2,6.
Conclusion 10. Let M be a connected simple matroid with more than one circuit, but M is not a line, then C2(M) is 2-connected.
引文
[1]B.Alspach and G. Liu. Paths and cycles in matroid base graphs, Graphs and combina-torics,1989,5(3),207-211.
[2]B. Bollobas, A lower bound for the number of nonisomorphic Matroids, J. Comb. Theory, 1969,7,366-368.
[3]J. A. Bondy, Transversal matroids, base orderable matroids and graphs, Quart. J. Math., 1972,23,81-89.
[4]J.A. Bondy, U.S.R. Murty, Graph Theory With Applications, American Elsevier, New York,1976.
[5]J. A. Bondy, A.W. Ingleton, Pancyclic graph II, J.Comb. Theory, B20,1976,41-46
[6]R. A. Brualdi, On foundamental transversal matroids, Proc. Amer. Math. Soc.,45 (1974), 151-156.
[7]R. A. Brualdi, G. W. Dinolt, Characterization of transversal matroids and their presenta-tions, J. Comb. Theory,12 (1972),268-286.
[8]M. Cai, A solution of Chartand's problem on spanning trees, Acta Mathematicae Appli-catae Sinica(English Ser.),1:2 (1984),97-98.
[9]P. A. Catlin, J. W. Grossman, A. M. Hobbs, and H. J. Lai. Fractional arboricity, strength, and principal partitions in graphs and matroids. Disc. Appl. Math.,40(1992),285-302.
[10]H. H. Crapo, Single element extensions of Matroids, J. Res. Nat. Bur. Stand.,69B (1965), 57-65.
[11]R. L. Cummins, Hamilton circuits in tree graphs. IEEE Trans Circuit theory,1 (1966), 82-90.
[12]H. Deng and R. Li. The 1-hamiltonian properties of matroid base graphs. Acta Scinat Univ Norm Hunan.,22(3)(1999),1-5.
[13]H. Deng and F. Xia. The P3-Hamiltonian property of matroid base graphs. Jour Nat Sci Hunan Norm Uni.,1 (2000),5-8.
[14]J. Donald, C. Holzmann and M. Tobey. A characterization of complete matroid base graphs, J. Comb. Theory Ser.,22B (1977),139-193.
[15]J. R. Edmonds, Minimum partition of a matroid into indedent subsets. J.Res. Natl. Bur. Stand.,69B(1965),67-72.
[16]J. R. Edmonds, Matroids and the greedy algorithm, Math Programming,1, (1971),127-136.
[17]V. Estivill-Castro, M. Noy and J. Urrutia, On the chromatic number of tree graphs. Dis-crete Math.,223 (2000),363-366
[18]J. Gao, Quasi-1-Hamilton connectedness of tree graphs. Math. Res. and Exposition,7(3) (1987),498.
[19]J. Gao,1-Hamilton connectedness of tree graphs. Mathematica Applicata.,6(2) (1993), 136-144.
[20]H. Harary, R. J. Mokken and M. J. Plantholt, Interpolation theorem for diameters of spanning trees. IEEE Trans Circuits and System,30 (1983),429-432.
[21]F. Harary and M. J. Plantholt, Classification of interpolation theorems for spanning trees and other families of spanning subgraphs. J. Graph Theory,13(6)(1989),703-712.
[22]K. Heinrich, G. Liu, A lower bound on the number of spanning trees with k end vertices. J. Graph Theory,12(1) (1988),95-100.
[23]C. A. Holzmann, F. Harary, On the tree graph of a matroid. SIAM J. Appl. Math.,22 (1972),187-193.
[24]C. A. Holzmann, P. G. Norton and M. D. Tobey. A graphical representation of matroids. SIAM J Appl Math.,29 (1973),618-672.
[25]A. W. Ingleton, Gammoids and transversal matroids,J. Comb. Theory,15 (1973),51-68.
[26]T. Kamae. The existence of Hamilton circuit in a tree graph. IEEE Trans Circuit theory, 14 (1967),279-283.
[27]G. Kishi and Y. Kajitani. On Hamilton circuits in a tree graphs. IEEE Trans Circuit theory,15 (1968),42-50.
[28]G. Kishi and Y. Kajitani. On Hamilton circuits in a tree graphs. IEEE Trans Circuit theory,15 (1968),271-273.
[29]E. Lawler. Combinatorial Optimization. John Wiley, New York,1972.
[30]李乐学,树图的Hamilton性质.山东工业大学学报,27(3)(1997),261-263.
[31]李乐学,刘桂真,邻接叶边交换森林图的连通性,山东大学学报,39(6)(2004),49-51.
[32]李乐学,卞秋菊,刘桂真,拟阵的基关联图,山东大学学报,40(2)(2005),24-40.
[33]L. Li and G. Liu, Matroids and Graphs, Ph.D. Dissertation, Shandong University,2005.
[34]X. Li. the connectivities of the SEE-graph and the AEE-graph for the connected span-ning k-edge subgraphs of a graph Discete Math.,183 (1998),237-245.
[35]X. Li, V. Neumann-Lara and E. Rivera-Campo, Two Approaches for the Generaliza-tion of Leaf Edge Exchange Graphs on Spanning Trees to Connected Spanning k-Edge Subgraphs of a Graph. Ars. combin.,75 (2005),257-265.
[36]G. Liu. The connectivities of matroid base graphs, J. Operations Research,3(1) (1984), 67-68.
[37]G. Liu, Matroids complexes-geometrical representations on matroids. Acta Math. Scien-tia,5 (1985),35-42.
[38]G. Liu, The Connectivities of Adjacent Tree Graphs. Acta Mathematicae Applicatae Sinica,3(4) (1987),313-317.
[39]G. Liu. A lower bound on connectivities of matroid base graphs, Discrete Math.,69(1) (1988),55-60.
[40]G. Liu. On connectivities of base graph of some matroids,J. Sys. Sci. and Math. Scis., 1(1) (1988),18-21.
[41]G. Liu, On connectivities of tree graphs, J. Graph Theory,12(3) (1988),453-459.
[42]G. Liu, The proof of a conjecture on matroid basis graphs. Scince Sinica,1990:593-599.
[43]G. Liu, L. Zhang, Forest graphs of graphs. Chinese Journal of Engineering Mathmatics, 22(6) (2005),1100-1109.
[44]L. Lovasz, A. Recski, On the sum of Matroids, Acta Math. Acad. Sci. Hung,24 (1973), 329-333.
[45]S. B. Maurer, Intervals in matroid basis graphs. Discrete Math.,11 (1975),147-159.
[46]S. B. Maurer, Matroid basis graphs Ⅰ, J.Comb. Theory B,14 (1973),216-240.
[47]S.B. Maurer, Matroid basis graphs Ⅱ,J. Comb. Theory B,15 (1973) 121-145.
[48]U. S. R. Murty, On the number of bases of matroid, Proc. Second Louisiana Conference on Combinatorics, (1971),387-410.
[49]G. J. Minty. On the axiamatic functions of the theories of directed linear graphs, electrical networks and network programming. J. Math. Mech.,3 (1966),485-520.
[50]U. S. R. Murty, On the number of bases of a Matroid, Proc. Second Louisiana on Com-binatorics. Louisiana State Univ. Baton Rouge, (1971),387-410.
[51]U.S.R. Murty, Extremal critically connected matroids, Discrete Math.,8 (1974),49-58.
[52]D. Naddef and W. R. Pulleyblank. Hamiltonicity and combinatorial polyhedra. J. Com-bin. theory B,31 (1981),279-312.
[53]C. St. J. A. Nash-Williams, Edge-disjiont spanning trees of finite graphs. J. London Math. Soc.,36 (1961),445-450.
[54]C. St. J. A. Nash-Williams, Decompositions of finite graphs. J. London Math. Soc.,39 (1964),12.
[55]J.G. Oxley, Matroid Theory, Oxford University Press, New York,1992.
[56]M. J. Piff, An upper bound for the number of matroids. J. Comb. Theory,13 (1973), 241-245.
[57]R. Rado, A theorem on independence relations. Quart. J. Math. Oxford Ser.,13 (1942), 83-89.
[58]H. Shank. Note on Hamilton circuits in tree graphs. IEEE Trans Circuit theory,15 (1967),86.
[59]W. T. Tutte, matroids and graphs, Trans. Amer. Math. Soc.,1959,90,527-552.
[60]W. T. Tutte, An algorithm for determining whether a given binary matroid is graphioc, Proc. Amer. Math. Soc.,11 (1960),905-917.
[61]W. T. Tutte, Lectures on matroids, J. Res. Nat. Bur. Stand.,69B (1965),1-48.
[62]W. T. Tutte, Connectivity in matroids, Canad J. Math,18 (1966),1301-1324.
[63]W. T. Tutte, Introduction to the Theory of Mattroids, American Elsevier 1970.
[64]D. J. A. Welsh, Euler and bipartite matroids. J. Comb. Theory,6 (1969),375-377.
[65]D. J. A. Welsh, On the hyperplanes of a matroid, Proc. Cambridge Phil Soc.,6 (1969), 11-18.
[66]D. J. A. Welsh, A bound for the number of matroids.J. Comb. Theory,6 (1969),313-316.
[67]D. J. A. Welsh, Matroid theory Academic Press. London,1976.
[68]N. L. White, A basis extension property.J.London Math. Soc.,202 (1975),79-95.
[69]H. Whitney, On the abstract properties of linear dependence. Amer. J. Math.,57 (1935), 509-533.
[70]R. J. Wilson, An introduction to matroid theory. Amer MathMonthly,80 (1973),500-525.
[71]D. R. Woodall, An exchange theorem for bases of matroids.J. Comb. Theory,16B (1974),227-229.
[72]D. R. Woodall, The induction of matroids by graphs, J.London Math Soc,10 (1975), 22-35.
[73]F. Zhang and Z. Chen. Connectivity of (adjacency) tree graphs. J. Xinjiang university, 3(4) (1986),1-5.
[74]H. Zheng and G. Liu. Some properties on paths in matroid base graphs. Systems Science and Mathematical Science,1(2) (1998),104-108.
[2]B. Bollobas, A lower bound for the number of nonisomorphic Matroids, J. Comb. Theory, 1969,7,366-368.
[3]J. A. Bondy, Transversal matroids, base orderable matroids and graphs, Quart. J. Math., 1972,23,81-89.
[4]J.A. Bondy, U.S.R. Murty, Graph Theory With Applications, American Elsevier, New York,1976.
[5]J. A. Bondy, A.W. Ingleton, Pancyclic graph II, J.Comb. Theory, B20,1976,41-46
[6]R. A. Brualdi, On foundamental transversal matroids, Proc. Amer. Math. Soc.,45 (1974), 151-156.
[7]R. A. Brualdi, G. W. Dinolt, Characterization of transversal matroids and their presenta-tions, J. Comb. Theory,12 (1972),268-286.
[8]M. Cai, A solution of Chartand's problem on spanning trees, Acta Mathematicae Appli-catae Sinica(English Ser.),1:2 (1984),97-98.
[9]P. A. Catlin, J. W. Grossman, A. M. Hobbs, and H. J. Lai. Fractional arboricity, strength, and principal partitions in graphs and matroids. Disc. Appl. Math.,40(1992),285-302.
[10]H. H. Crapo, Single element extensions of Matroids, J. Res. Nat. Bur. Stand.,69B (1965), 57-65.
[11]R. L. Cummins, Hamilton circuits in tree graphs. IEEE Trans Circuit theory,1 (1966), 82-90.
[12]H. Deng and R. Li. The 1-hamiltonian properties of matroid base graphs. Acta Scinat Univ Norm Hunan.,22(3)(1999),1-5.
[13]H. Deng and F. Xia. The P3-Hamiltonian property of matroid base graphs. Jour Nat Sci Hunan Norm Uni.,1 (2000),5-8.
[14]J. Donald, C. Holzmann and M. Tobey. A characterization of complete matroid base graphs, J. Comb. Theory Ser.,22B (1977),139-193.
[15]J. R. Edmonds, Minimum partition of a matroid into indedent subsets. J.Res. Natl. Bur. Stand.,69B(1965),67-72.
[16]J. R. Edmonds, Matroids and the greedy algorithm, Math Programming,1, (1971),127-136.
[17]V. Estivill-Castro, M. Noy and J. Urrutia, On the chromatic number of tree graphs. Dis-crete Math.,223 (2000),363-366
[18]J. Gao, Quasi-1-Hamilton connectedness of tree graphs. Math. Res. and Exposition,7(3) (1987),498.
[19]J. Gao,1-Hamilton connectedness of tree graphs. Mathematica Applicata.,6(2) (1993), 136-144.
[20]H. Harary, R. J. Mokken and M. J. Plantholt, Interpolation theorem for diameters of spanning trees. IEEE Trans Circuits and System,30 (1983),429-432.
[21]F. Harary and M. J. Plantholt, Classification of interpolation theorems for spanning trees and other families of spanning subgraphs. J. Graph Theory,13(6)(1989),703-712.
[22]K. Heinrich, G. Liu, A lower bound on the number of spanning trees with k end vertices. J. Graph Theory,12(1) (1988),95-100.
[23]C. A. Holzmann, F. Harary, On the tree graph of a matroid. SIAM J. Appl. Math.,22 (1972),187-193.
[24]C. A. Holzmann, P. G. Norton and M. D. Tobey. A graphical representation of matroids. SIAM J Appl Math.,29 (1973),618-672.
[25]A. W. Ingleton, Gammoids and transversal matroids,J. Comb. Theory,15 (1973),51-68.
[26]T. Kamae. The existence of Hamilton circuit in a tree graph. IEEE Trans Circuit theory, 14 (1967),279-283.
[27]G. Kishi and Y. Kajitani. On Hamilton circuits in a tree graphs. IEEE Trans Circuit theory,15 (1968),42-50.
[28]G. Kishi and Y. Kajitani. On Hamilton circuits in a tree graphs. IEEE Trans Circuit theory,15 (1968),271-273.
[29]E. Lawler. Combinatorial Optimization. John Wiley, New York,1972.
[30]李乐学,树图的Hamilton性质.山东工业大学学报,27(3)(1997),261-263.
[31]李乐学,刘桂真,邻接叶边交换森林图的连通性,山东大学学报,39(6)(2004),49-51.
[32]李乐学,卞秋菊,刘桂真,拟阵的基关联图,山东大学学报,40(2)(2005),24-40.
[33]L. Li and G. Liu, Matroids and Graphs, Ph.D. Dissertation, Shandong University,2005.
[34]X. Li. the connectivities of the SEE-graph and the AEE-graph for the connected span-ning k-edge subgraphs of a graph Discete Math.,183 (1998),237-245.
[35]X. Li, V. Neumann-Lara and E. Rivera-Campo, Two Approaches for the Generaliza-tion of Leaf Edge Exchange Graphs on Spanning Trees to Connected Spanning k-Edge Subgraphs of a Graph. Ars. combin.,75 (2005),257-265.
[36]G. Liu. The connectivities of matroid base graphs, J. Operations Research,3(1) (1984), 67-68.
[37]G. Liu, Matroids complexes-geometrical representations on matroids. Acta Math. Scien-tia,5 (1985),35-42.
[38]G. Liu, The Connectivities of Adjacent Tree Graphs. Acta Mathematicae Applicatae Sinica,3(4) (1987),313-317.
[39]G. Liu. A lower bound on connectivities of matroid base graphs, Discrete Math.,69(1) (1988),55-60.
[40]G. Liu. On connectivities of base graph of some matroids,J. Sys. Sci. and Math. Scis., 1(1) (1988),18-21.
[41]G. Liu, On connectivities of tree graphs, J. Graph Theory,12(3) (1988),453-459.
[42]G. Liu, The proof of a conjecture on matroid basis graphs. Scince Sinica,1990:593-599.
[43]G. Liu, L. Zhang, Forest graphs of graphs. Chinese Journal of Engineering Mathmatics, 22(6) (2005),1100-1109.
[44]L. Lovasz, A. Recski, On the sum of Matroids, Acta Math. Acad. Sci. Hung,24 (1973), 329-333.
[45]S. B. Maurer, Intervals in matroid basis graphs. Discrete Math.,11 (1975),147-159.
[46]S. B. Maurer, Matroid basis graphs Ⅰ, J.Comb. Theory B,14 (1973),216-240.
[47]S.B. Maurer, Matroid basis graphs Ⅱ,J. Comb. Theory B,15 (1973) 121-145.
[48]U. S. R. Murty, On the number of bases of matroid, Proc. Second Louisiana Conference on Combinatorics, (1971),387-410.
[49]G. J. Minty. On the axiamatic functions of the theories of directed linear graphs, electrical networks and network programming. J. Math. Mech.,3 (1966),485-520.
[50]U. S. R. Murty, On the number of bases of a Matroid, Proc. Second Louisiana on Com-binatorics. Louisiana State Univ. Baton Rouge, (1971),387-410.
[51]U.S.R. Murty, Extremal critically connected matroids, Discrete Math.,8 (1974),49-58.
[52]D. Naddef and W. R. Pulleyblank. Hamiltonicity and combinatorial polyhedra. J. Com-bin. theory B,31 (1981),279-312.
[53]C. St. J. A. Nash-Williams, Edge-disjiont spanning trees of finite graphs. J. London Math. Soc.,36 (1961),445-450.
[54]C. St. J. A. Nash-Williams, Decompositions of finite graphs. J. London Math. Soc.,39 (1964),12.
[55]J.G. Oxley, Matroid Theory, Oxford University Press, New York,1992.
[56]M. J. Piff, An upper bound for the number of matroids. J. Comb. Theory,13 (1973), 241-245.
[57]R. Rado, A theorem on independence relations. Quart. J. Math. Oxford Ser.,13 (1942), 83-89.
[58]H. Shank. Note on Hamilton circuits in tree graphs. IEEE Trans Circuit theory,15 (1967),86.
[59]W. T. Tutte, matroids and graphs, Trans. Amer. Math. Soc.,1959,90,527-552.
[60]W. T. Tutte, An algorithm for determining whether a given binary matroid is graphioc, Proc. Amer. Math. Soc.,11 (1960),905-917.
[61]W. T. Tutte, Lectures on matroids, J. Res. Nat. Bur. Stand.,69B (1965),1-48.
[62]W. T. Tutte, Connectivity in matroids, Canad J. Math,18 (1966),1301-1324.
[63]W. T. Tutte, Introduction to the Theory of Mattroids, American Elsevier 1970.
[64]D. J. A. Welsh, Euler and bipartite matroids. J. Comb. Theory,6 (1969),375-377.
[65]D. J. A. Welsh, On the hyperplanes of a matroid, Proc. Cambridge Phil Soc.,6 (1969), 11-18.
[66]D. J. A. Welsh, A bound for the number of matroids.J. Comb. Theory,6 (1969),313-316.
[67]D. J. A. Welsh, Matroid theory Academic Press. London,1976.
[68]N. L. White, A basis extension property.J.London Math. Soc.,202 (1975),79-95.
[69]H. Whitney, On the abstract properties of linear dependence. Amer. J. Math.,57 (1935), 509-533.
[70]R. J. Wilson, An introduction to matroid theory. Amer MathMonthly,80 (1973),500-525.
[71]D. R. Woodall, An exchange theorem for bases of matroids.J. Comb. Theory,16B (1974),227-229.
[72]D. R. Woodall, The induction of matroids by graphs, J.London Math Soc,10 (1975), 22-35.
[73]F. Zhang and Z. Chen. Connectivity of (adjacency) tree graphs. J. Xinjiang university, 3(4) (1986),1-5.
[74]H. Zheng and G. Liu. Some properties on paths in matroid base graphs. Systems Science and Mathematical Science,1(2) (1998),104-108.