Mathematics – Combinatorics
Scientific paper
2011-07-27
Mathematics
Combinatorics
v1: 19 pages, 1 figure. v2: 20 pages, 1 figure. v3:29 pages, no figures. v3 includes an account of the relationship between th
Scientific paper
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\'{a}s and Sorkin [Combinatorica 24 (2004), 567-584].
Brijder Robert
Traldi Lorenzo
No associations
LandOfFree
The adjacency matroid of a graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The adjacency matroid of a graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The adjacency matroid of a graph will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-113430