Properties Of Intersection Graphs Of Bases Of Matroids

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)|<k, and for each vertex v∈V(G),(?)f(v)=0. It is well know that a graph G has a nowhere-zero Zk-flow if and only if there is a nowhere-zero k-flow in G.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.