The adjacency matroid of a graph

From MaRDI portal

MaRDI QIDQ396844zbMATH OpenFDO

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)

Full work available at URL https://arxiv.org/abs/1107.5493, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p27

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


zbMATH Keywords

adjacencydelta-matroidinterlace polynomiallocal complementmatroidminorTutte polynomial

Mathematics Subject Classification ID

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


Abstract: If G is a looped graph, then its adjacency matrix represents a binary matroid MA(G) on V(G). MA(G) may be obtained from the delta-matroid represented by the adjacency matrix of G, but MA(G) is less sensitive to the structure of G. Jaeger proved that every binary matroid is MA(G) for some G [Ann. Discrete Math. 17 (1983), 371-376]. The relationship between the matroidal structure of MA(G) and the graphical structure of G has many interesting features. For instance, the matroid minors MA(G)−v and MA(G)/v are both of the form MA(Gprime−v) where Gprime 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].


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)].


Recommendations


Cites work


Cited in
(12)








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)

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=The_adjacency_matroid_of_a_graph&oldid=61621821"
Powered by MediaWiki