Connectivity And Hamiltonian Properties Of Second-order Circuit Graphs And Second-order Intersection Graphs Of Bases Of Matroids

Graph theory is an important subject in the study of discrete mathematics.In the 1930s,Whitney first introduced the concept of matroid theory through an axiomatic generalization of the theory of cycle space and bond spaces in graph theory and linear independence in linear algebra.The matroid theory has developed rapidly in the 20th century and is widely used in many fields.The base graph,base incidence graph,circuit graph and intersection graph of base of matroid are the study areas of the matroid theory,reflecting the structural properties of the matroid theory and its base and circuit.At present,there are few studies on the second-order intersection graphs of bases and second-order circuit graphs of matroids.Based on the previous work,this thesis studies that the connectivity and Hamiltonian properties of second-order intersection graphs of bases of general matroids,properties of the Hamiltonian connection and 1-vertex-fault-tolerant Hamiltonian of second-order intersection graphs of bases of uniform matroids and the connectivity and Hamiltonian properties of second-order circuit graphs of cycle matroids of complete bipartite.In this thesis,we first give a lower bound of the connectivity of the second-order intersection graphs of bases of matroids,and prove that the second-order intersection graphs G^Ⅱ（M）of bases of general matroid M is both positively and negatively Hamiltonian（that is,uniformly Hamiltonian）and edge-pancyclic.Secondly,on the uniform matroid with good properties,we give the exact connectivity of the second-order intersection graphs G^Ⅱ(U_4,n)of bases of the uniform matroid U_4,n,and prove that the second-order intersection graphs G^Ⅱ(U_m,n)of bases of the uniform matroid U_m,n is Hamiltonian connected,1-vertex-fault-tolerant Hamiltonian and 1vertex-fault-tolerant positively and negatively Hamiltonian（namely,1-vertex-faulttolerant uniformly Hamiltonian）.And for any two edges e₁ and e₂ in G^Ⅱ(U_4,n),there is a Hamiltonian circuit that does not include them,and there is a Hamiltonian circuit that includes e₁ but does not include e₂.Finally,the second-order circuit graphs of a class of graphic matroids are studied.It is found that the second-order circuit graphs C₂(M(K_2,n))of cycle matroid of complete bipartite graph K_2,n are edgepancyclic,and the connectivity is（2n-4）.On the basis of proving that the second-order circuit graphs C₂(M(K_2,n))and C₂(M(K_3,n))of cycle matroids of K_2,n and K_3,n are Hamiltonian and Hamiltonian connected,the second-order circuit graphs C₂(M(K_m,n)of cycle matroids of K_m,n are proved to be Hamiltonian and Hamiltonian connected by mathematical induction.