The Properties of Graphs of Matroids
Ping Li, Guizhen Liu · InTech eBooks · 2012
components of M. The base graph of matroid M is a graph G B (M) with vertex set V(G B ) and edge set E(G B ) such that V(G B )=B and E(G B )={BB ′ | B, B ′ ∈B, ||B -B ′ | = 1}.Let G be a graph.The vertex set and edge set of a graph G are denoted by V(G) and E(G), respectively.If A ⊆ V(G), then G[A] denotes the induced subgraph of G by A.Ak-path is a path of k-edges and denoted by P k .Ak-circuit is a circuit of k-edges and denoted by C k .K n denotes the complete graph of order n.A graph is Hamiltonian connected if for any two vertices there is a Hamilton path connects them.A graph is Hamiltonian if it contains a Hamilton circuit.A graph G is positively Hamiltonian, written G ∈ H + , if for every edge of G, there is a Hamilton circuit containing it.G is negatively Hamiltonian, written G ∈ H -,if for every edge of G, there is a Hamilton circuit avoiding it.When G ∈ H + and G ∈ H -,we say that G is uniformly Hamiltonian.If for every edge e of G, there is a k-circuit containing it for anyLet G be a simple graph of order at least 3 vertices.Then graph G is called p 3 -Hamilton, if for any path P with 3 vertices, there exists a Hamilton cycle of G which contains P. If for any two vertices v 1 and v 2 and any edge v 2 v 3 where v 1 = v 3 , graph G has a Hamilton path from v 1 to v 2 and such that edge v 2 v 3 in this path, then we say that graph G is 1-Hamilton connected.Terminology and notations not defined here can be found in [1] and [2].Maurer defined the base graph of a matroid , and discussed the graphical properties of the base graph of a matroid [3][4].Cummins showed that every matroid base graph with at least three vertices has a Hamilton circuit [5].Holzmann and Harary showed that for every edge in a base graph there is a Hamilton circuit containing it and another Hamilton circuit avoiding it [6].Alspach and Liu studied the properties of paths and circuits in base graphs of matroids [7].The connectivity of the base graph of matroids is investigated by Liu [8].The other graphical properties of the base graphs of matroid have also been investigated by .Now we give a new concept as follows.The circuit graph of a matroid M is a graphwhere the same notation is used for the vertices of G and the circuits of M. We give another new graph related to the bases of matroids as follows.The intersection graph of bases of matroid M =( E, B) is a graph G I (M) with vertex set V(G I ) and edge set E(G I ) such that V(G I )=B and E(G I )={BB ′ : |B ∩ B ′ | = 0, B, B ′ ∈B(M)}, where the same notation is used for the vertex of G I and the base of M. The properties of paths , cycles and the connectivity of circuit graphs of matroids are discussed in this chapter.In particular, some new results obtained by us are given. Preliminary resultsTo prove the main theorem we need the following preliminary results.Lemma 2.1.[17] A matroid M is connected if and only if for every pair e 1 , e 2 of distinct elements of E, there is a circuit containing both e 1 and e 2 .Lemma 2.2.[17] If M is a connected matroid, then for every e ∈ E, either M/e or M\e is also connected.