| 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 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 relationship of different bases, thus 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.A matroid M is a finite set E together with a nonempty collection B of subsets of E such that the following conditions are satisfied. For any Bi,B2∈B and any element∈E B1\B2, there exists an element y∈B2\B1such that (B1\{e})∪{y}∈B. The matroid is denoted by M=[E,B). Each member of B is called a base of M.Any subsets of a base of M is called an independent set. If C C E is not an independent set and any C’(?) C is an independent set, then C is called a circuit 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 element{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-circuit and loops. If an element is contained in every base of M, then we call it a coloop of M.If S is a subset of E, such that every circuit of M is contained in S or contained in E\S, then S is called a separated set of M. A minimal nonempty separated set of M is called a component of M. If a matroid M has only one component, then M is called a connected matroid. Let e be any element of M, then we use M/e and M\e to denote the matroid obtained from M by contracting and deleting e, respectively. A matroid obtained from M by limited times of contractions and limited times of deletion is called a minor of matroid M.The base graph of a matroid M=(E, B) is a graph G such that V(G)=B and E(G)={B B’:B,B’∈B, and|B\B’|=1} where the same notation is used for the vertices of G and the bases 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. A graph G is called edge-Hamiltonian or positively Hamilton, written G∈H+, if every edge of G is contained in a Hamilton cycle. G is negatively Hamilton, written G∈Ⅱ-, if for each edge of G there is a Hamilton cycle avoiding it. When G∈H+and G∈G H-, we say that G is uniformly Hamilton.A graph G is called E2-Hamiltonian if every two edges of G are contained in a Hamilton cycle of G. Let G be a simple graph of order at least3, G is called P3-Hamiltonian if each path on three vertices is contained in a Hamilton cycle of G. G is called1-Hamilton connected if, for each pair of vertices v1and v2and any edge v2v3(where v1≠v3), there exists a Hamilton path of G from v1to v2traversing v2v3.Let G be a graph. If there is a subset F(?)V(G) and|F|≤f, such that G-F is hamiltonian, then G is called f-vertex-fault-tolerant Hamiltonian. Similarly, we can define the concepts of f-vertex-fault-tolerant edge-Hamiltonian and f-vertex-fault-tolerant Hamiltonian connected.The thesis is divided into three chapters. A short but relatively complete survey about tree graph, forest graphs and matroid base graphs is given in Chapter1. We discuss the Hamiltonian properties of matroid base graph in Chapter2. In Chapter3, the vertex-fault-tolerant Hamiltonian property is studied firstly.In the following, we will list our main results in this thesis. Conclusion1. Let G be the base graph of any simple matroid M. If|V(G)|≥5and there is no minor N of M such that the base graph of matroid N is isomorphic to W5, then for any edges e and e’, G has a Hamilton cycle containing e and excluding e’.Conclusion2. Suppose that G is the base graph of any matroid with|V(G)|≥4and N={M|M is a matroid, every component of which a pair of parallel elements or a coloop and M has at least two pair two pair of parallel elements}. If M(?)N, then G is1-vertex-fault-tolerant Hamiltonian.Conclusion3. Let G be the base graph of a simple matroid M. There are at least four vertices in G. Then G is1-vertex-fault-tolerant edge-Hamiltonian.Conclusion4. Let G be the base graph of a simple matroid M. There are at least three vertices in G. Then G is1-vertex-fault-tolerant Hamiltonian connected.Conclusion5. Let G be the base graph of a simple matroid M. There are at least five vertices in G. Then G is2-vertex-fault-tolerant Hamiltonian. |
PDF Full Text Request