Ore-type and Dirac-type theorems for matroids |
| |
Authors: | Sean McGuinness |
| |
Institution: | aDept. of Mathematics, Thompson Rivers University, McGill Road, Kamloops, BC V2C 5N3, Canada |
| |
Abstract: | Let M be a connected binary matroid having no -minor. Let be a collection of cocircuits of M. We prove there is a circuit intersecting all cocircuits of if either one of two things hold:- (i) For any two disjoint cocircuits and in it holds that .
- (ii) For any two disjoint cocircuits and in it holds that .
Part (ii) implies Ore's Theorem, a well-known theorem giving sufficient conditions for the existence of a hamilton cycle in a graph. As an application of part (i), it is shown that if M is a k-connected regular matroid and has cocircumference c*2k, then there is a circuit which intersects each cocircuit of size c*−k+2 or greater.We also extend a theorem of Dirac for graphs by showing that for any k-connected binary matroid M having no -minor, it holds that for any k cocircuits of M there is a circuit which intersects them. |
| |
Keywords: | Matroid Regular matroid |
本文献已被 ScienceDirect 等数据库收录! |
|