Some Properties Of Circuit Graphs Of Matroids

Matroid theory dates from the 1930's and Whitney in his basic paper [69] con-ceived a matroid as an abstract generalization of a matrix. Matroid theory gives us powerful techniques for understanding combinatorial optimization problems and for de-signing polynomial-time algorithms. 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, so 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. In order to study the properties of circuits of matroids, we give a new definition as circuit graph of matroid, and give some properties of this graph.Let E be a finite set of elements.For S1,S2,S2 (?) E, set S1-S2={x(?)x∈S1andx (?) S2}. Let(?) be a collection of non-null subsets of E which satisfies the following two axioms:(C1) A proper subset of a member of(?) is not a member of (?).(C2) If a∈C1 n C2 and b∈C1-C2 where C1,C2∈(?) and a,b∈E, then there exists a C3∈V such that b∈C3 c (C1 (?) C2)-{α}.Then M= (E, (?)) is called a matroid on E. We refer to the members of(?) as circuits of matroid M. The family of circuits of M determines a matroid.A subset of E that does not contain any circuit is called an independent set of M. A maximal independent set is called a basis of M, denoted by B(M). Let(?)(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' in B'such that B∪{b'}-{b} is also a basis.Let M=(E,(?)) be a matroid. If X (?) E, then the matroid on E-X whose circuits are those of M which are contained in E-X is called the restriction of M to E-X (or the matroid obtained by deleting X from M) and is denoted by M\X or M(?)(E-X).There is another derived matroid of importance. If X (?) E, then the family of minimal non-empty intersections of E-X with circuits of M is the family of circuits of a matroid on E-X called the contraction of M to E-X (or the matroid obtained by contracting X out of M) and is denoted by M/X.If X={e}, we use M\e and M/e to denote the matroid obtained from M by delet-ing and contracting e, respectively. A matroid obtained from M by limited times of contractions and limited times of deletions is called a minor matroid of M.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. Ifφand 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 no 2-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 M be a matroid and let (?) denote the family of bases of M. Let (?) denote the family of complements of members of (?) in E. Then (?) is the family of bases of a matroid, denoted by M*, called the dual of M. The circuits of M* are called the co-circuits of M.(?)(M\e)={B(?)B(?)B∈(?)M), e(?)B} and (?)(M/e)={B-{e}(?)B∈(?)(M), e∈B}.A walk in a graph G is an alternating sequence of vertices and edges such that ei is an edge joining vi and vi+1. For simplicity, P=ν0ν1…νκ+1will be written thereby implying the occurrences of the edges. If Q=νκ+1νκ+2…νn is a walk, then If P=ν0,e0,ν1, e1,…,νκ,eκ,νκ+1,is a walk in which all the vertices are distinct, then P is called a path. Ifν0,ν1,…,νκ+1 are distinct andν0=νκ+1, then P is called a cycle. The length of a walk is the number of edges contained in the sequence.A family of paths in G is said to be internally-disjoint if no vertex of G is an internal vertex of more than one path of the family.A vertex cut of G is a subsetν' ofνsuch that G-ν' is disconnected. Aκ-vertex cut is a vertex cut of k elements. The only graphs which do not have vertex cuts are those that contain complete graphs as spanning subgraphs. If G has at least one pair of distinct nonadjacent vertices, the connectivityκ(G) of G is the minimum k for which G has a k-vertex cut; otherwise, we defineκ(G) to be(?)ν(G)(?)-1. We call a graph with just one vertex trivial and all other graphs nontrivial. Thusκ(G)=0 if G is either trivial or disconnected. G is said to beκ-connected ifκ(G)≥κ. All nontrivial connected graphs are 1-connected.For subsets S and S'of V(G), we denote by [S,S'] the set of edges with one end in S and the other in S'. An edge cut of G is a subset of E(G) of the form [S,S], where S is a nonempty proper subset of V(G) and (?)= V\S. Aκ-edge cut is an edge cut of k elements. If G is nontrivial and E' is an edge cut of G, then G-E'is disconnected. We then define the edge connectivityκ'(G) of G to be the minimum k for which G has aκ-edge cut. G is said to beκ-edge-connected ifκ'(G)≥k.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.A graph G with n vertices is called vertex-pancyclic if for any integer k,3≤k≤n, and any vertex of G, the vertex lies in 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.Now we give a new concept as follows. 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)=(?) and E(G)={CC'| C, C'∈(?),|C∩C'|≠0}, where the same notation is used for the vertices of G and the circuits of M.The kth order circuit graph Ck(M) of M has vertex set V(Cκ(M))=(?)(M), the set of all circuits of M. Two vertices C, C'∈(?)(M) are adjacent in Cκ(M) if and only if (?)C∩C'(?) k. For notational convenience, for a circuit C∈(?)(M), we shall use C to denote both a vertex in Cκ(M) and a circuit (also as a subset of E(M)) of M.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 connectivities of matroid circuit graphs in Chapter 2. In Chapter 3, some properties of the cycles in circuit graphs of matroids are given. Paths in matroid circuit graphs are studied in Chapter 4. In Chapter 5, we give a new concept as kth order circuit graph of a matroid M, and studied its connectivities and diameter.In the following, we will list our main results in this thesis.Conclusion 1. Suppose that G=G(M) is the circuit graph of a connected matroid M. Then the connectivityκ(G)≥2(?)E-B(?)-2, where B is a base of M..Conclusion 2. Suppose that G=G(M) is the circuit graph of a connected matroid M with minimum degreeδ(G). Thenδ(G)≥2(?)E-B(?)-2.Conclusion 3. Suppose that G=G(M) is the circuit graph of a connected matroid M with minimum degreeδ(G). Then the edge connectivityκ'(G)=κ(G).Conclusion 4. For any connected matroid M=(E, I) which has at least three circuits, the circuit graph G=G(M) is edge-pancyclic. Conclusion 5. For any connected matroid M, the circuit graph G(M) is uniformly Hamilton whenever G(M) contains at least four vertices.Conclusion 6. Let G be the circuit graph of a connected matroid M=(E, I). If (?)V(G)(?)= n andκ1+κ2+…κp= n where ki is an integer and ki≥3, i=1,2,…,p, then G has a 2-factor F containing p vertex-disjoint cycles D1,D2,…, Dp such that the length of Di is ki(i= 1,2,…, p).Conclusion 7. Let M=(E,(?)) be a connected matroid with at least three circuits. If G=G(M) is the circuit graph of M, then the diameter of G is at most 2. Furthermore, d(G(M))=2 if and only if there exist two circuits such that they have no element in common.Conclusion 8. Let G=G(M) be the circuit graph of a connected matroid M=(E,(?)). If|V(G)|= n and C1,C2∈V(G), then there is a path of length k joining C1and C2 for any k satisfying 2≤κ≤n-1.Conclusion 9. Let M be a connected simple matroid. Each of the following holds. (i) C2(M) is connected. (ii) If M has no restriction isomorphic to U2.6, then every pair of nonadjacent vertices C1 and C2 in C2(M) has a common neighbor C3. (iii)The diameter of C2(M) is at most two if and only if for any X (?) E, the restriction of M to X is not isomorphic to U2,6.Conclusion 10. Let M be a connected simple matroid with more than one circuit, but M is not a line, then C2(M) is 2-connected.