Bouchet (1987) defined delta-matroids by relaxing the base exchange axiom of matroids.
Oum (2009) introduced a graphic delta-matroid from a pair of a graph and its vertex subset.
We define a $\Gamma$-graphic delta-matroid for an abelian group $\Gamma$, which generalizes a graphic delta-matroid.
For an abelian group $\Gamma$, a $\Gamma$-labelled graph is a graph whose vertices are labelled by elements of $\Gamma$.
We prove that a certain collection of edge sets of a $\Gamma$-labelled graph forms a delta-matroid, which we call a $\Gamma$-graphic delta-matroid, and provide a polynomial-time algorithm to solve the separation problem, which allows us to apply the symmetric greedy algorithm of Bouchet (1987) to find a maximum weight feasible set in such a delta-matroid.
We also prove that a $\Gamma$-graphic delta-matroid is a graphic delta-matroid if and only if it is even.
We prove that every $\mathbb{Z}_p^k$-graphic delta matroid is represented by some symmetric matrix over a field of characteristic of order $p^k$, and if every $\Gamma$-graphic delta-matroid is representable over a finite field $\mathbb{F}$, then $\Gamma$ is isomorphic to $\mathbb{Z}_p^k$ and $\mathbb{F}$ is a field of order $p^\ell$ for some prime $p$ and positive integers $k$ and $\ell$.
This is joint work with Duksang Lee and Sang-il Oum.
|
