Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949674 | Discrete Applied Mathematics | 2017 | 18 Pages |
Abstract
In the 1930s Hassler Whitney considered and completely solved the problem (WP) of describing the classes of graphs G having the same cycle matroid M(G) Whitney (1932, 1933). A natural analog (WP)â² of Whitney's problem (WP) is to describe the classes of graphs G having the same matroid Mâ²(G), where Mâ²(G) is a matroid (on the edge set of G) distinct from M(G). For example, the corresponding problem (WP)â²=(WP)θ for the so-called bicircular matroid Mθ(G) of graph G was solved in Coullard et al. (1991) and Wagner (1985). We define the so-called k-circular matroid Mk(G) on the edge set of graph G for any integer kâ¥0 so that M(G)=M0(G) and Mθ(G)=M1(G). We give a characterization and establish some important properties of the k-circular matroid Mk(G). The results of this paper are used in our paper De Jesús and Kelmans (2017) to study a particular problem of (WP)k on graphs uniquely defined by their k-circular matroids.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
José F. De Jesús, Alexander Kelmans,