Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

On connectivity in matroids and graphs


Author: James G. Oxley
Journal: Trans. Amer. Math. Soc. 265 (1981), 47-58
MSC: Primary 05B35; Secondary 05C40
DOI: https://doi.org/10.1090/S0002-9947-1981-0607106-5
MathSciNet review: 607106
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we derive several results for connected matroids and use these to obtain new results for -connected graphs. In particular, we generalize work of Murty and Seymour on the number of two-element cocircuits in a minimally connected matroid, and work of Dirac, Plummer and Mader on the number of vertices of degree two in a minimally $ 2$-connected graph. We also solve a problem of Murty by giving a straightforward but useful characterization of minimally connected matroids. The final part of the paper gives a matroid generalization of Dirac and Plummer's result that every minimally $ 2$-connected graph is $ 3$-colourable.


References [Enhancements On Off] (What's this?)

  • [1] B. Bollobás, Extremal graph theory, London Math. Soc. Mono., no. 11, Academic Press, London, New York and San Francisco, 1978. MR 506522 (80a:05120)
  • [2] J. A. Bondy and U. S. R. Murty, Graph theory with applications, Macmillan, London; American Elsevier, New York, 1976. MR 0411988 (54:117)
  • [3] T. H. Brylawski, A combinatorial model for series-parallel networks, Trans. Amer. Math. Soc. 154 (1971), 1-22. MR 0288039 (44:5237)
  • [4] H. H. Crapo and G.-C. Rota, On the foundations of combinatorial theory: combinatorial geometries, Preliminary ed., MIT Press, Cambridge, Mass. and London, 1970. MR 0290980 (45:74)
  • [5] G. A. Dirac, Minimally $ 2$-connected graphs, J. Reine Angew. Math. 228 (1967), 204-216. MR 0216975 (36:70)
  • [6] J. E. Graver and M. E. Watkins, Combinatorics with emphasis on the theory of graphs, Springer-Verlag, New York, Heidelberg and Berlin, 1977. MR 0505525 (58:21632)
  • [7] R. Halin, Untersuchungen über minimale $ n$-fach zusammenhängende Graphen, Math. Ann. 182 (1969), 175-188. MR 0278979 (43:4705)
  • [8] W. Mader, Ecken vom Grad $ n$ in minimalen $ n$-fach zusammenhängenden Graphen, Arch. Math. (Basel) 23 (1972), 219-224. MR 0306043 (46:5170)
  • [9] -, Connectivity and edge-connectivity in finite graphs, Surveys in Combinatorics (B. Bollobás, ed.), Cambridge Univ. Press, New York, 1979, pp. 66-95. MR 561307 (81d:05044)
  • [10] U. S. R. Murty, Extremal critically connected matroids, Discrete Math. 8 (1974), 49-58. MR 0349446 (50:1940)
  • [11] J. G. Oxley, Colouring, packing and the critical problem, Quart. J. Math. Oxford Ser. (2) 29 (1978), 11-22. MR 0505704 (58:21734)
  • [12] -, On a covering problem of Mullin and Stanton for binary matroids, Aequationes Math. 20 (1980), 104-112. MR 569956 (81g:05049)
  • [13] -, A generalization of a covering problem of Mullin and Stanton for matroids, Proc. Sixth Austral. Combinatorics Conf., Lecture Notes in Math., vol. 748, Springer-Verlag, Berlin, Heidelberg and New York, 1979, pp. 92-97. MR 558036 (81f:05058)
  • [14] -, On matroid connectivity, Quart. J. Math. Oxford Ser. (2) (to appear). MR 615194 (82g:05040)
  • [15] -, On $ 3$-connected matroids, Canad. J. Math, (to appear).
  • [16] M. D. Plummer, On minimal blocks, Trans. Amer. Math. Soc. 134 (1968), 85-94. MR 0228369 (37:3950)
  • [17] P. D. Seymour, Matroid representation over $ GF(3)$, J. Combin. Theory. Ser. B 26 (1979), 159-173. MR 532586 (80k:05031)
  • [18] -, Packing and covering with matroid circuits, J. Combin. Theory Ser. B 28 (1980), 237-242. MR 572476 (81j:05046)
  • [19] -, Decomposition of regular matroids, J. Combin. Theory Ser. B 28 (1980), 305-359. MR 579077 (82j:05046)
  • [20] W. T. Tutte, Connectivity in matroids, Canad. J. Math. 18 (1966), 1301-1324. MR 0205880 (34:5706)
  • [21] -, Wheels and whirls, Lecture Notes in Math., vol. 211, Springer-Verlag, Berlin, Heidelberg and New York, 1971, pp. 1-4. MR 0321767 (48:134)
  • [22] P. N. Walton and D. J. A. Welsh, On the chromatic number of binary matroids, Mathematika 27 (1980), 1-9. MR 581990 (81m:05060)
  • [23] D. J. A. Welsh, Matroid theory, London Math. Soc. Mono., no. 8, Academic Press, London, New York and San Francisco, 1976. MR 0427112 (55:148)
  • [24] N. L. White, The bracket ring of a combinatorial geometry. II: Unimodular geometries, Trans. Amer. Math. Soc. 214 (1975), 233-248. MR 0447023 (56:5338)
  • [25] P.-K. Wong, On certain $ n$-connected matroids, J. Reine Angew. Math. 299/300 (1978), 1-6. MR 0498195 (58:16350)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05B35, 05C40

Retrieve articles in all journals with MSC: 05B35, 05C40


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1981-0607106-5
Article copyright: © Copyright 1981 American Mathematical Society

American Mathematical Society