The adjacency matroid of a graph

zbMATH Open1298.05210arXiv1107.5493MaRDI QIDQ396844FDOQ396844

Authors: L. Traldi, Robert Brijder, Hendrik Jan Hoogeboom 

Publication date: 14 August 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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 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, 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 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'{a}s and Sorkin [Combinatorica 24 (2004), 567-584].

Full work available at URL: https://arxiv.org/abs/1107.5493

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Binary matroids and local complementation
• Adjacency in binary matroids
• Adjoints of binary matroids
• Isotropic matroids. I: Multimatroids and neighborhoods
• On Tutt's Characterization of graphic matroids—a graphic proof

zbMATH Keywords

minormatroidTutte polynomialadjacencydelta-matroidinterlace polynomiallocal complement

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph polynomials (05C31) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Theory of Matroids
• Title not available (Why is that?)
• Binary nullity, Euler circuits and interlace polynomials
• Title not available (Why is that?)
• The group structure of pivot and loop complementation on graphs and set systems
• Representability of \(\bigtriangleup\)-matroids over \(GF(2)\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Determinantal ideals, Pfaffian ideals, and the principal minor theorem
• The interlace polynomial of graphs at \(-1\)
• A multivariate interlace polynomial and its computation for graphs of bounded clique-width
• Isotropic systems
• A generalization of Tutte's characterization of totally unimodular matrices
• Interlace polynomials
• On the interlace polynomials
• Title not available (Why is that?)
• Title not available (Why is that?)
• Weighted interlace polynomials
• Structural Analysis of Complex Networks
• Structural Analysis of Complex Networks
• Symmetric Representations of Binary Matroids
• Interlace polynomials for multimatroids and delta-matroids
• On the Principal Edge Tripartition of a Graph
• Coverings and delta-coverings
• Nullity and loop complementation for delta-matroids
• Distance Hereditary Graphs and the Interlace Polynomial
• Interlacement in 4-regular graphs: a new approach using nonsymmetric matrices
• Title not available (Why is that?)
• Flots et tensions dans un graphe
• A two-variable interlace polynomial
• On the linear algebra of local complementation
• The interlace polynomial of a graph
• Graphes de cordes et espaces graphiques

Cited In (12)

• Adjacency Matrices
• Recombination faults in gene assembly in ciliates modeled using multimatroids
• Title not available (Why is that?)
• Title not available (Why is that?)
• Commutativity of the adjacency matrices of graphs
• Representation theorems for simplicial complexes and matroidal-like properties of minimal partitioners
• Isotropic matroids. II: Circle graphs
• Binary matroids and local complementation
• The transition matroid of a 4-regular graph: an introduction
• How many delta-matroids are there?
• Isotropic matroids. I: Multimatroids and neighborhoods
• Adjacency in binary matroids

This page was built for publication: The adjacency matroid of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396844)