On the interplay between embedded graphs and delta-matroids
2019
The mutually enriching relationship between graphs and matroids has motivated discoveries
in both fields. In this paper, we exploit the similar relationship between embedded graphs and
delta-matroids. There are well-known connections between geometric duals of plane graphs and
duals of matroids. We obtain analogous connections for various types of duality in the literature
for graphs in surfaces of higher genus and delta-matroids. Using this interplay, we establish a
rough structure theorem for delta-matroids that are twists of matroids, we translate Petrie duality
on ribbon graphs to loop complementation on delta-matroids, and we prove that ribbon graph
polynomials, such as the Penrose polynomial, the characteristic polynomial, and the transition
polynomial, are in fact delta-matroidal. We also express the Penrose polynomial as a sum of
characteristic polynomials.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
25
References
5
Citations
NaN
KQI