2015/07/05 by Rintaro Ikeshita, Shin‐ichi Tanigawa, Ikeshita, Rintaro +1
Computer Science · #05B35 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.1507.01259
openalex publication_date 2015/07/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G=(V,E) is called (k,ℓ)-sparse if |F|≤ k|V(F)|-ℓ for any nonempty F⊆ E, where V(F) denotes the set of vertices incident to F. It is known that the family of the edge sets of (k,ℓ)-sparse subgraphs forms the family of independent sets of a matroid, called the (k,ℓ)-count matroid of G. In this paper we shall investigate lifts of the (k,ℓ)-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|≤ k|V(F)|-ℓ +αψ(F) for some function αψ determined by a given group labeling ψ on E.