Circuits through cocircuits in a graph with extensions to matroids

被引:4
作者
Mcguinness, S
机构
[1] Syosset, NY 11791
关键词
05C38; 05B35;
D O I
10.1007/s00493-005-0027-5
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We show that for any k-connected graph having cocircumference c*, there is a cycle which intersects every cocycle of size c* - k + 2 or greater. We use this to show that in a 2-connected graph, there is a family of at most c* cycles for which each edge of the graph belongs to at least two cycles in the family. This settles a question raised by Oxley. A certain result known for cycles and cocycles in graphs is extended to matroids. It is shown that for a k-connected regular matroid having circumference c >= 2k if C-1 and C-2 are disjoint circuits satisfying r(C-1) + r(C-2) = r(C-1 boolean OR C-2), then \C-perpendicular to\ + \C-2\ <= 2(c - k + 1).
引用
收藏
页码:451 / 463
页数:13
相关论文
empty
未找到相关数据