On connectivity in matroids and graphs

Oxley, James G.

doi:10.1090/S0002-9947-1981-0607106-5

On connectivity in matroids and graphs
HTML articles powered by AMS MathViewer

by James G. Oxley PDF

Trans. Amer. Math. Soc. 265 (1981), 47-58 Request permission

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

Béla Bollobás, Extremal graph theory, London Mathematical Society Monographs, vol. 11, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978. MR 506522
J. A. Bondy and U. S. R. Murty, Graph theory with applications, American Elsevier Publishing Co., Inc., New York, 1976. MR 0411988
Thomas H. Brylawski, A combinatorial model for series-parallel networks, Trans. Amer. Math. Soc. 154 (1971), 1–22. MR 288039, DOI 10.1090/S0002-9947-1971-0288039-7
Henry H. Crapo and Gian-Carlo Rota, On the foundations of combinatorial theory: Combinatorial geometries, Preliminary edition, The M.I.T. Press, Cambridge, Mass.-London, 1970. MR 0290980
G. A. Dirac, Minimally $2$-connected graphs, J. Reine Angew. Math. 228 (1967), 204–216. MR 216975, DOI 10.1515/crll.1967.228.204
Jack E. Graver and Mark E. Watkins, Combinatorics with emphasis on the theory of graphs, Graduate Texts in Mathematics, Vol. 54, Springer-Verlag, New York-Berlin, 1977. MR 0505525
R. Halin, Untersuchungen über minimale $n$-fach zusammenhängende Graphen, Math. Ann. 182 (1969), 175–188 (German). MR 278979, DOI 10.1007/BF01350321
W. Mader, Ecken vom Grad $n$ in minimalen $n$-fach zusammenhängenden Graphen, Arch. Math. (Basel) 23 (1972), 219–224 (German). MR 306043, DOI 10.1007/BF01304873
W. Mader, Connectivity and edge-connectivity in finite graphs, Surveys in combinatorics (Proc. Seventh British Combinatorial Conf., Cambridge, 1979) London Math. Soc. Lecture Note Ser., vol. 38, Cambridge Univ. Press, Cambridge-New York, 1979, pp. 66–95. MR 561307
U. S. R. Murty, Extremal critically connected matroids, Discrete Math. 8 (1974), 49–58. MR 349446, DOI 10.1016/0012-365X(74)90109-5
James G. Oxley, Colouring, packing and the critical problem, Quart. J. Math. Oxford Ser. (2) 29 (1978), no. 113, 11–22. MR 505704, DOI 10.1093/qmath/29.1.11
James G. Oxley, On a covering problem of Mullin and Stanton for binary matroids, Aequationes Math. 20 (1980), no. 1, 104–112. MR 569956, DOI 10.1007/BF02190499
James G. Oxley, A generalization of a covering problem of Mullin and Stanton for matroids, Combinatorial mathematics, VI (Proc. Sixth Austral. Conf., Univ. New England, Armidale, 1978) Lecture Notes in Math., vol. 748, Springer, Berlin, 1979, pp. 92–97. MR 558036
James G. Oxley, On matroid connectivity, Quart. J. Math. Oxford Ser. (2) 32 (1981), no. 126, 193–208. MR 615194, DOI 10.1093/qmath/32.2.193

On

-connected matroids

Michael D. Plummer, On minimal blocks, Trans. Amer. Math. Soc. 134 (1968), 85–94. MR 228369, DOI 10.1090/S0002-9947-1968-0228369-8
P. D. Seymour, Matroid representation over $\textrm {GF}(3)$, J. Combin. Theory Ser. B 26 (1979), no. 2, 159–173. MR 532586, DOI 10.1016/0095-8956(79)90055-8
P. D. Seymour, Packing and covering with matroid circuits, J. Combin. Theory Ser. B 28 (1980), no. 2, 237–242. MR 572476, DOI 10.1016/0095-8956(80)90067-2
P. D. Seymour, Decomposition of regular matroids, J. Combin. Theory Ser. B 28 (1980), no. 3, 305–359. MR 579077, DOI 10.1016/0095-8956(80)90075-1
W. T. Tutte, Connectivity in matroids, Canadian J. Math. 18 (1966), 1301–1324. MR 205880, DOI 10.4153/CJM-1966-129-2
W. T. Tutte, Wheels and whirls, Théorie des matroïdes (Rencontre Franco-Britannique, Brest, 1970), Lecture Notes in Math., Vol. 211, Springer, Berlin, 1971, pp. 1–4. MR 0321767
P. N. Walton and D. J. A. Welsh, On the chromatic number of binary matroids, Mathematika 27 (1980), no. 1, 1–9. MR 581990, DOI 10.1112/S0025579300009876
D. J. A. Welsh, Matroid theory, L. M. S. Monographs, No. 8, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. MR 0427112
Neil L. White, The bracket ring of a combinatorial geometry. II. Unimodular geometries, Trans. Amer. Math. Soc. 214 (1975), 233–248. MR 447023, DOI 10.1090/S0002-9947-1975-0447023-4
Pak Ken Wong, On certain $n$-connected matroids, J. Reine Angew. Math. 299(300) (1978), 1–6. MR 498195, DOI 10.1515/crll.1978.299-300.1