Back to Search
Start Over
Count Matroids of Group-Labeled Graphs
- Publication Year :
- 2015
-
Abstract
- A graph $G=(V,E)$ is called $(k,\ell)$-sparse if $|F|\leq k|V(F)|-\ell$ for any nonempty $F\subseteq E$, where $V(F)$ denotes the set of vertices incident to $F$. It is known that the family of the edge sets of $(k,\ell)$-sparse subgraphs forms the family of independent sets of a matroid, called the $(k,\ell)$-count matroid of $G$. In this paper we shall investigate lifts of the $(k,\ell)$-count matroid by using group labelings on the edge set. By introducing a new notion called near-balancedness, we shall identify a new class of matroids, where the independence condition is described as a count condition of the form $|F|\leq k|V(F)|-\ell +\alpha_{\psi}(F)$ for some function $\alpha_{\psi}$ determined by a given group labeling $\psi$ on $E$.
- Subjects :
- Mathematics - Combinatorics
05B35
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1507.01259
- Document Type :
- Working Paper