The adjacency matroid of a graph

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

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)

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

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

Cites work

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

Cited in

(12)

• Adjacency Matrices
• Recombination faults in gene assembly in ciliates modeled using multimatroids
• scientific article; zbMATH DE number 146675 (Why is no real title available?)
• scientific article; zbMATH DE number 2068375 (Why is no real title available?)
• Commutativity of the adjacency matrices of graphs
• Isotropic matroids. II: Circle graphs
• Representation theorems for simplicial complexes and matroidal-like properties of minimal partitioners
• 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)