<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
An Erdos-Gallai Theorem for Matroids
Sean McGuinness
Department of Mathematics, Thompson Rivers University, Kamloops, BC V2C5N3, Canada
smcguinness@tru.ca
Annals of Combinatorics 16 (1) pp.107-119 March, 2012
AMS Subject Classification: 05D15; 05B35
Abstract:
Erdos and Gallai showed that for any simple graph with n vertices and circumference c it holds that |E(G)| ≤ 1/ 2 (n−1)c. We extend this theorem to simple binary matroids having no F7-minor by showing that for such a matroid M with circumference c(M) ≥ 3 it holds that |E(M)| ≤ 1/ 2 r(M)c(M).
Keywords: matroid, binary matroid, minor

References:

1. Anderson, I.: Combinatorics of Finite Sets. Dover Publications, Inc., Mineola, NY (2002)

2. Bollobás B.: Modern Graph Theory. Springer-Verlag, New York (1998)

3. Bondy, J.A.: Small cycle double covers of graphs. In: Hahn, G., Sabidussi, G., Woodrow, R. (eds.) Cycles and Rays, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., 301, pp. 21–40. Kluwer Acad. Publ., Dordrecht (1990)

4. Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. American Elsevier Publishing Co., Inc., New York (1976)

5. Dilworth, R.P.: A decomposition theorem for partially ordered sets. Ann. of Math. (2) 51, 161–166 (1950)

6. Erd˝os, P., Gallai, T.: On maximal paths and circuits of graphs. Acta Math. Hungar. 10(3-4), 337–356 (1959)

7. Lemos M., and Oxley J.: A sharp bound on the size of a connected matroid. Trans. Amer. Math. Soc. 353(10), 4039–4056 (2001)

8. McGuinness, S.: Cycle and cocycle coverings of graphs. J. Graph Theory 65(4), 270–284 (2010)

9. Murty, U.S.R.: Extemal matroids with forbidden restrictions and minors. In: Hoffmann, F. et al. (eds.) Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp. 463–468. Utilitas Mathematica Publishing Inc., Winnipeg, Man. (1976)

10. Oxley J.: Matroid Theory. Oxford University Press, New York (1992)

11. Pyber, L.: An Erdos-Gallai conjecture. Combinatorica 5(1), 67–79 (1985)

12. Seymour, P.D.: Decomposition of regular matroids. J. Combin. Theory Ser. B 28(3), 305–359 (1980)

13. Wu P.-L.: An upper bound on the number of edges of a 2-connected graph. Combin. Probab. Comput. 6(1), 107–113 (1997)