| Full text | |
| Author(s): |
Total Authors: 2
|
| Affiliation: | [1] Univ Fed Pernambuco, Dept Matemat, BR-50740540 Recife, PE - Brazil
Total Affiliations: 1
|
| Document type: | Journal article |
| Source: | Linear Algebra and its Applications; v. 432, n. 1, p. 259-274, JAN 1 2010. |
| Web of Science Citations: | 2 |
| Abstract | |
For a 3-connected binary matroid M, let dim(A)(M) be the dimension of the subspace of the cocycle space spanned by the non-separating cocircuits of M avoiding A, where A subset of E(M). When A = empty set, Bixby and Cunningham, in 1979, showed that diM(A)(M) = r(M). In 2004, when vertical bar A vertical bar = 1, Lemos proved that dim(A) M = r(M) - 1. In this paper, we characterize the 3-connected binary matroids having a pair of elements that meets every non-separating cocircuit. Using this result, we show that 2 dim(A) (M) >= r(M) - 3, when M is regular and vertical bar A vertical bar = 2. For vertical bar A vertical bar = 3, we exhibit a family of cographic matroids with a 3-element set intersecting every non-separating cocircuit. We also construct the matroids that attains McNulty and Wu's bound for the number of non-separating cocircuits of a simple and cosimple connected binary matroid. (C) 2009 Elsevier Inc. All rights reserved. (AU) | |
| FAPESP's process: | 03/09925-5 - Foundations of computer science: combinatory algorithms and discrete structures |
| Grantee: | Yoshiharu Kohayakawa |
| Support Opportunities: | PRONEX Research - Thematic Grants |