Representations Of Lift Bicircular Matroids

Hassler Whitney introduced matroid theory first in 1935.His initial purpose was to find out the similarities of various concepts of dependence in algebra and graph theory,and described its axiom system.Almost all the conclusions without involving vertex in graph theory and all the results of linear independence without involving some specific field in algebra can be described by matroids.In the paper was entieled "An Introduction to Matroid Theory",R.J.Wilson had commented that:Matroid theory can be used to simplify various ideas in graph theory and transversal theory.Matroid theory is far from being 'generalization for generalization's sake',matroid theory gives us a deeper insight into several problems in transversal theory,as well as including among its applications simple proofs of results in graph theory which are awkward to prove by more traditional methods.Besides,there is also a close relationship between matroid theory and geometry,topology,combinatorial optimization,theoretical physics.Lift bicircular matroids are a class of matroids defined on the edge set of a graph.For a given graph G,the circuits of its lift bicircular matroid L(G)are the edge sets of those subgraphs of G that contain at least two cycles,and are minimal with respect to this property.That is,the circuits of L(G)consists of the edge sets of two edge-disjoint cycles with at most one common vertex,or three internally disjoint paths between a pair of distinct vertices.Lift bicircular matroids are a special class of lift matroids that arises from biased graphs.Biased graphs and lift matroids were introduced by Zaslavsky in[17,18].In this thesis,we give a characterization of when two graphs give rise to the same lift bicircular matoid,which answers a question proposed by Irene Pivotto.In particular,aside from some appropriately defined "small" graphs,two graphs have the same lift bicicular matroid if and only if they are 2-isomorphic in the sense of Whitney.We use two strategys to prove our resultThe thesis is organised as follows.In Chapter 1,some basic definitions and re-lated results are given.In Chapter 2,the first proof is given.We first consider the 3-connected cases,and then using decomposition theory we extended the result to 2-connected cases.In Chapter 3,the second proof is given.We first consider graphs with at most five vertices,and then use induction to prove the final result.Finally,In Chapter 4,further research work is given.