Matroids And Graphs

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, thus 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. These graphs are very useful in combinatorial theory, network design, computer science and so on. We pay our attention to the base graph , the base incidence graph of a matroid , the adjacency leaf exchange forest graph of a graph and the fractional arboricities of graphs and so on.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 B₁, B₂ ∈ B and any element e₁ ∈ B₁\B₂, there exists an element e₂ ∈ B₂\B₁ such that (B₁\e₁)Ue₂ ∈ 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 (?) E is not an independent set and any X (?) 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 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. If an elemen is contained in every base of M. then we call it a cocircuit 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 MAe 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 matroid of Af.The base graph of a matroid M = (E, B) is a graph G such that V(G) = B and E{G) = {BB' : 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 if every edge of G is contained in a Hamilton cycle. A graph G is called ^-Hamiltonian if every two edges of G are contained in a Hamilton cycle of G. Let G be a simple graph of order at least 3, G is called P3-Hamiltonian if each path on three vertices is contained in a Hamilton cycle of G. G is called 1-Hamilton connected if, for each pair of vertices v\ and v^ and any edge v?yz (where v% ^ v\), there exists a Hamilton path of G from i>i to vi traversing 1^3.A graph G with n vertices is cailed vertex-pancyclic if for any integer k, 3 < k < n, and any vertex of G, the vertex lies n 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.Let M = (E,B) be a matroid, where E = {ei,e2,...,en}, B = {Bi,B2,... ,Bm}, and m,n are positive integers, the rank of M is p — p{M). The base incidence graph of M is a bipartite graph, denoted by A(M) = A(E,B,F), where E, B are the bipartition of A(M), F = {e,Bj| t{ € Bj, i = 1,'?,...,n; j = 1,2,...,m) is the edge set of A(M).Let G be a connected graph. The tree graph of G is defined to be a graph T{G), whose vertices are the spanning trees of G such that two vertices are adjacent if their corresponding spanning trees have exactly two edges in their symmetric differences. The adjacency tree graph, denoted by X,j((?), is a spanning subgraph of the tree graph in which two vertices are adjacent if the only two edges in their symmetric differences of their corresponding spanning trees a-e adjacent in G. The leaf exchange tree graph is a spanning subgraph of the adjacency tree graph, and its two vertices are adjacent if the only two edges in their symmetric differences of their corresponding spanning trees areleaves of their corresponding spanning trees, respectively. The adjacency leaf exchange tree graph is a spanning subgraph of the adjacency tree graph, its two vertices are adjacent if the only two edges in their symmetric differences of their corresponding spanning trees are leaves of their corresponding spanning trees, respectively.The single edge exchange graph SEE-graph of a graph G is defined on the set of all connected spanning fc-edge subgraphs of G, the vertices of the SEE-graph of G are the spanning &-edge subgraphs of G such that two vertices are adjacent if their corresponding spanning fc-edge subgraphs have exactly two edges in their symmetric differences; The AEE-graph, the adjacency edge exchange graph, which is a spanning subgraph of the SEE-graph, defined also on the set of all connected spanning fc-edge subgraphs of G, two vertices are adjacent if the only two edges in their symmetric differences of their corresponding spanning Ar-edge subgraphs of G axe adjacent in G.Let G be a connected graph and let v = \V(G)\, u is an integer such that 1 < u> < u — 1. The forest graph FU(G) of G, is defined as follows, the vertices of F^{G) are the set of all spanning forests with u> components; two vertices of FW{G) are adjacent if their corresponding spanning forests have exactly two edges in their symmetric differences. Obviously, if u = v, then FU(G) is taivially K\. Hence in the following we let 1 < u> < v — 1. If u> = 1, then FU(G) is T(G), the tree graph of G. One can easily see that if to = v - 1, then FU{G) is K€. where e = \E{G)\.Fï¿¡(G), the adjacency forest graph of G is a spanning subgraph of F^(G), its two vertices are adjacent if the the only two edges in the symmetric differences of their corresponding spanning forests with u components of G are adjacent in G.The leaf exchange forest graph of G, denoted by F^G), is defined to be the spanning subgraph of FUJ(G), its two vertices are adjacent if and only if the two edges in the symmetric differences of their corresponding spanning forests with u components of G are leaves of the two forests, respectively.The adjacency leaf exchange forest graph of G, denoted by F°l(G), is defined to be the spanning subgraph of both F^(G) and Fï¿¡(G) such that two vertices are adjacent if and only if the two edges in the symetric difference of their corresponding forests with ui components of G are leaves of the two forests, respectively, and adjacent in G.Suppose that we wish to decompose the edge set of a graph G into acyclic subsets, i.e., if G = (V, E), we want to find Ei,E2,... ,Ek C E, such that(1) each of the subgraphs G = (V,Ei) is acyclic,(2) E = EiUE2U...UEk.The smallest size of such a decomposition is called the arboricity(or edge-aboricity) of G, and is denoted by T(G). If G is connected, the aboricity is also the minimum number of spanning trees of G that include all edges of G.Similarly, if G = (V, E), we want to find E\, E%,..., E^ C E, such that(1) each of the subgraphs Gi = (V, E1,) is acyclic and the number of edges in G{ = (V, Ei) is not more than u(G) - u>, and(2) E = EiUE2U...UEk.Obviously, the largest Gi = {V,Ei) is a spanning forest of G with u components. The smallest number of sets E\,E<2,..., ï¿¡* is called the w-arboricity (or oj-dge-aboricity) of G, and is denoted by TU,(G). If G is connected, the u;-aboricity is also the minimum number of spanning forests of G with u> components that include all edges of G.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 ï¿¡?2-Hamiltonian properties of matroid base graphs in Chapter 2. In Chapter 3, the base incidence graph of a matroid is introduced by us for the first time. The connectivities, the diameters and the matchings of this graph are studied in this chapter. Paths and cycles in matroid base graphs are studied in Chapter 4. In Chapter 5, we study the connectivities of the adjacency leaf exchange forest graphs and discuss the chromatic numbers of matroid base graphs, forest graphs and other related graphs. In Chapter 6, two definitions, w-arboricity and fractional u/'-arboricity of a connected graph are defined, and formulas which can caculate the w-arboricity and the fractional u-arboricity of a connected graph are obtained also.In the following, we will list our main results in this thesis.Conclusion 1. Let M = (E, B) hi a matroid and G = G(M) be the base graph of matroid M. If Ad = (E,B) has at least three bases and there is no minor N of M = {E,B) such that the base graph G(N) of matroid N is isomorphic to W5, then G = G(M) is E^-Hamiltonian..Conclusion 2. Let M - (E, B) be a simple matroid M with rank p — p(M). Let A(M) be the base incidence graph of and the minimum degree of A(M) is 6 = 6(A(M)). If p = p(M) is at least 2, then the connectivity of A(M) is equal to its minimum degree 5 .Conclusion 3. Let M = {E,B) be a simple matroid with rank p = p(M) > 2. Let A(M) = A(E,B,F) be the base incidence graph of M, then the diameter o/A(M) is at most 4, i.e., d(A(M)) < 4. Furthermore, d(A(M)) — A. if and only if there exist two bases such that they have no elements in common.Conclusion 4. Let M = (E, B) be a simple matroid such that every element of E is contained in a circuit of M and let A(M) = A(E,B,Jr) be the base incidence graph of M. Then there exists a matching in A(M) covering all elements of E.Conclusion 5. Let M = {E,B) be a simple matroid on E . If G is the base graph of M, and k is a positive integer, k < ^i/(G(M)), then G has a path P and a cycle C such that V{G) = V(C)\JV(P), V(C)f]V(P) = and u{P) = k.Conclusion 6. Let M = (E, B) be a simple matroid on E and G be the base graph of M. If M has at least two circuits and the minimum circuit of M = (E, B) has at least four elements, then G has two independent cycles C\ and C^ such that v{C\) = v(Ci) or u(d) + 1 = u(C2), and V(G) = V(Cx)[)V(C2),Conclusion 7. Let G = G(V,E) be a 2-connected graph and let u = \V(G)\. Given an integer u> such that 1 < u> < v — 1, let F^{G) be the adjacency leaf exchange forest graph ofG. ThenFï¿¡l(G) is connected.Conclusion 8. Let M = (E, B) be a simple matroid and G — G{M) be the base graph of M. Then x(G(M)) < \E\. This bound can not be improved in general.Conclusion 9. Let G be a connected graph. Fï¿¡(G) be the adjacency forest graph of G, 1 < uj < v — 1. Then x(Fï¿¡(G)) < x'{G), where x'{G) ^s the edge-chromatic number of G. This bound cannot be improved in general.Conclusion 10. Let G be a 2-connected graph with maximum degree A and letbe the adjacency forest graph ofG, \.Conclusion 12. Let G = (V, E) be a connected graph. If u is a positive integer such that 1 < u < v — 1. thenwhere the maximum is over all ac% die subgraphs of H such that the number of the components of H is at least u>.