On graphs uniquely defined by their -circular matroids

详细信息    查看全文

• 作者：José ; F. De Jesú ; s^a ; Alexander Kelmans^a ; ^b ; ^{kelmans.alexander@gmail.com}
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P3
• 页码：474-487
• 全文大小：639 K
• 卷排序：217

文摘

In 1930s Hassler Whitney considered and completely solved the problem (WP)(WP) of describing the classes of graphs GG having the same cycle matroid M(G)M(G) (Whitney, 1933; Whitney, 1932). A natural analog (WP)′(WP)′ of Whitney’s problem (WP)(WP) is to describe the classes of graphs GG having the same matroid M′(G)M′(G), where M′(G)M′(G) is a matroid (on the edge set of GG) distinct from M(G)M(G). For example, the corresponding problem (WP)′=(WP)θ(WP)′=(WP)θ for the so-called bicircular matroid Mθ(G)Mθ(G) of graph GG was solved in Coulard et al. (1991) and Wagner (1985). In De Jesús and Kelmans (2015) we introduced and studied the so-called kk-circular matroids Mk(G)Mk(G) for every non-negative integer kk that is a natural generalization of the cycle matroid M(G):=M0(G)M(G):=M0(G) and of the bicircular matroid Mθ(G):=M1(G)Mθ(G):=M1(G) of graph GG. In this paper (which is a continuation of our paper De Jesús and Kelmans (2015)) we establish some properties of graphs guaranteeing that the graphs are uniquely defined by their kk-circular matroids.