The adjacency matroid of a graph

Lorenzo Traldi¹ ; Robert Brijder² ; Hendrik Jan Hoogeboom³

¹Lafayette College
²Hasselt University and Transnational University of Limburg, Belgium
³LIACS, Leiden University, The Netherlands

The electronic journal of combinatorics, Tome 20 (2013) no. 3

Résumé

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$. Jaeger proved that every binary matroid is $M_{A}(G)$ for some $G$ [Ann. Discrete Math. 17 (1983), 371-376]. 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), 195-226]. 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 Arratia, Bollobás and Sorkin [Combinatorica 24 (2004), 567-584].

Détail

DOI : 10.37236/2911

Classification : 05C50, 05B35, 05C31, 05B20
Mots-clés : adjacency, delta-matroid, interlace polynomial, local complement, matroid, minor, Tutte polynomial