Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/15500

Title: The adjacency matroid of a graph
Authors: BRIJDER, Robert
Hoogeboom, Hendrik Jan
Traldi, Lorenzo
Issue Date: 2013
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(G′ − v) where G′ 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 -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´as and Sorkin [Combinatorica 24 (2004), 567-584].
Notes: Brijder, R (reprint author), Hasselt Univ, Diepenbeek, Belgium. robert.brijder@uhasselt.be; h.j.hoogeboom@cs.leidenuniv.nl; traldil@lafayette.edu
URI: http://hdl.handle.net/1942/15500
Link to publication: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p27
ISI #: 000323793600002
ISSN: 1077-8926
Category: A1
Type: Journal Contribution
Validation: ecoom, 2014
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A398.04 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.