On packing minors into connected matroids

被引:12
作者
Lemos, M
Oxley, J
机构
[1] Univ Fed Pernambuco, Dept Matemat, BR-50740540 Recife, PE, Brazil
[2] Louisiana State Univ, Dept Math, Baton Rouge, LA 70803 USA
关键词
D O I
10.1016/S0012-365X(98)00055-7
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let N be a matroid with k connected components and M be a minor-minimal connected matroid having N as a minor. This note proves that \E(M) - E(N)\ is at most 2k - 2 unless N or its dual is free, in which case \E(M) - E(N)\ less than or equal to k - 1. Examples are given to show that these bounds are best possible for all choices for N. A consequence of the main result is that a minimally connected matroid of rank r and maximum circuit size c has at most 2r - c + 2 elements. This bound sharpens a result of Murty. (C) 1998 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:283 / 289
页数:7
相关论文
共 8 条
[1]   COMBINATORIAL MODEL FOR SERIES-PARALLEL NETWORKS [J].
BRYLAWSKI, T .
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1971, 154 (FEB) :1-+
[2]   DECOMPOSITION FOR COMBINATORIAL GEOMETRIES [J].
BRYLAWSKI, TH .
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1972, 171 (SEP) :235-282
[3]  
DIRAC GA, 1967, J REINE ANGEW MATH, V228, P204
[4]  
Murty U. S. R., 1974, Discrete Mathematics, V8, P49, DOI 10.1016/0012-365X(74)90109-5
[5]  
Oxley J., 1993, MATROID THEORY
[6]   ON CONNECTIVITY IN MATROIDS AND GRAPHS [J].
OXLEY, JG .
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1981, 265 (01) :47-58
[7]   NOTE ON PRODUCTION OF MATROID MINORS [J].
SEYMOUR, PD .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1977, 22 (03) :289-295
[8]  
TRUEMPER K, 1984, EUROPEAN J COMBIN, V3, P377