The adjacency matroid of a graph (Q396844): Difference between revisions

Summary: 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 delta-matroid represented by the adjacency matrix of \(G\), but \(M_{A}(G)\) is less sensitive to the structure of \(G\). \textit{F. Jaeger} proved that every binary matroid is \(M_{A}(G)\) for some \(G\) [Discrete Math. 17, 371--376 (1983; Zbl 0521.05024)]. 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 \textit{P. Rosenstiehl} and \textit{R. C. Read} [Ann. Discrete Math. 3, 195--226 (1978; Zbl 0392.05059)]. Several of these results are given two very different proofs, the first involving linear algebra and the second involving set systems or delta-matroids. Also, the Tutte polynomials of the adjacency matroids of \(G\) and its full subgraphs are closely connected to the interlace polynomial of \textit{R. Arratia} et al. [Combinatorica 24, No. 4, 567--584 (2004; Zbl 1064.05139)].