The adjacency matroid of a graph

Abstract

If G is a looped graph, then its adjacency matrix represents a binary matroid MA(G) on V (G). MA(G) may be obtained from the delta-matroid represented by the adjacency matrix of G, but MA(G) is less sensitive to the structure of G. Jaeger proved that every binary matroid is MA(G) for some G [Ann. Discrete Math. 17 (1983), 371-376]. The relationship between the matroidal structure of MA(G) and the graphical structure of G has many interesting features. For instance, the matroid minors MA(G) − v and MA(G)/v are both of the form MA(G′ − v) where G′ may be obtained from G using local complementation. In addition, matroidal considerations lead to a principal vertex tripartition, distinct from the principal edge tripartition of Rosenstiehl and Read [Ann. Discrete Math. 3 (1978), 195-226]. Several of these results are given two very different proofs, the first involving linear algebra and the second involving set systems or -matroids. Also, the Tutte polynomials of the adjacency matroids of G and its full subgraphs are closely connected to the interlace polynomial of Arratia, Bollob´as and Sorkin [Combinatorica 24 (2004), 567-584].