
Lorenzo Traldi

Robert Brijder

Hendrik Jan Hoogeboom
Keywords:
adjacency, deltamatroid, interlace polynomial, local complement, matroid, minor, Tutte polynomial
Abstract
If $G$ is a looped graph, then its adjacency matrix represents a binary matroid $M_{A}(G)$ on $V(G)$. $M_{A}(G)$ may be obtained from the deltamatroid represented by the adjacency matrix of $G$, but $M_{A}(G)$ is less sensitive to the structure of $G$. Jaeger proved that every binary matroid is $M_{A}(G)$ for some $G$ [Ann. Discrete Math. 17 (1983), 371376]. The relationship between the matroidal structure of $M_{A}(G)$ and the graphical structure of $G$ has many interesting features. For instance, the matroid minors $M_{A}(G)v$ and $M_{A}(G)/v$ are both of the form $M_{A}(G^{\prime}v)$ where $G^{\prime}$ may be obtained from $G$ using local complementation. In addition, matroidal considerations lead to a principal vertex tripartition, analogous in some ways to the principal edge tripartition of Rosenstiehl and Read [Ann. Discrete Math. 3 (1978), 195226]. Several of these results are given two very different proofs, the first involving linear algebra and the second involving set systems or deltamatroids. Also, the Tutte polynomials of the adjacency matroids of $G$ and its full subgraphs are closely connected to the interlace polynomial of Arratia, Bollobás and Sorkin [Combinatorica 24 (2004), 567584].