The adjacency matroid of a graph
type: Item
instance of: scholarly article
title: The adjacency matroid of a graph
zbMATH Open document ID: 1298.05210
author: L. Traldi
author: Robert Brijder
author: Hendrik Jan Hoogeboom
published in: The Electronic Journal of Combinatorics
publication date: 2014-08-14T00:00:00Z
full work available at URL: https://arxiv.org/abs/1107.5493
full work available at URL: v20i3p27
review text: 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)].
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 05C31
Mathematics Subject Classification ID: 05B20
zbMATH DE Number: 6330299
zbMATH Keywords: adjacency
zbMATH Keywords: delta-matroid
zbMATH Keywords: interlace polynomial
zbMATH Keywords: local complement
zbMATH Keywords: matroid
zbMATH Keywords: minor
zbMATH Keywords: Tutte polynomial
MaRDI profile type: Publication
arXiv ID: 1107.5493
cites work: Interlace polynomials
cites work: Q4952623
cites work: The interlace polynomial of a graph
cites work: A two-variable interlace polynomial
cites work: The interlace polynomial of graphs at \(-1\)
cites work: Q4398864
cites work: Q5635462
cites work: Isotropic systems
cites work: Q3490007
cites work: Coverings and delta-coverings
cites work: Representability of \(\bigtriangleup\)-matroids over \(GF(2)\)
cites work: The group structure of pivot and loop complementation on graphs and set systems
cites work: Nullity and Loop Complementation for Delta-Matroids
cites work: Interlace polynomials for multimatroids and delta-matroids
cites work: A multivariate interlace polynomial and its computation for graphs of bounded clique-width
cites work: Structural Analysis of Complex Networks
cites work: Distance Hereditary Graphs and the Interlace Polynomial
cites work: Flots et tensions dans un graphe
cites work: A generalization of Tutte's characterization of totally unimodular matrices
cites work: Symmetric Representations of Binary Matroids
cites work: Graphes de cordes et espaces graphiques
cites work: Q3222218
cites work: Q3517562
cites work: Q5545293
cites work: Q5390304
cites work: Q4172067
cites work: On the Principal Edge Tripartition of a Graph
cites work: Weighted Interlace Polynomials
cites work: Binary nullity, Euler circuits and interlace polynomials
cites work: On the linear algebra of local complementation
cites work: On the interlace polynomials
cites work: Interlacement in 4-regular graphs: a new approach using nonsymmetric matrices
cites work: Q3216652
cites work: Q4111952
cites work: Theory of Matroids
cites work: Q3028888
cites work: Q3997906
description: scientific article; zbMATH DE number 6330299