Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-06T01:01:25.584Z Has data issue: false hasContentIssue false

On a matroid generalization of graph connectivity

Published online by Cambridge University Press:  24 October 2008

James G. Oxley
Affiliation:
Australian National University, Canberra

Extract

This paper relates the concept of n-connection for graphs to Tutte's theory of n-connection for matroids (12). In particular, we show how Tutte's definition may be modified to give a matroid concept directly generalizing the graph-theoretic notion of n-connection.

Type
Research Article
Copyright
Copyright © Cambridge Philosophical Society 1981

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

(1)Bondy, J. A. and Murty, U. S. R.Graph theory with applications (Macmillan, London; American Elsevier, New York, 1976).CrossRefGoogle Scholar
(2)Graver, J. E. and Watkins, M. E.Combinatorics with emphasis on the theory of graphs (Springer-Verlag, Berlin, Heidelberg, New York, 1977).CrossRefGoogle Scholar
(3)Inukai, T. and Weinberg, L.Theorems on matroid connectivity. Discrete Math. 22 (1978), 311312.Google Scholar
(4)Murty, U. S. R.Extremal critically connected matroids. Discrete Math. 8 (1974), 4958.CrossRefGoogle Scholar
(5)Oxley, J. G.On matroid connectivity. Quart. J. Math. Oxford (to appear).Google Scholar
(6)Oxley, J. G.On 3-connected matroida. Canad. J. Math. (to appear).Google Scholar
(7)Oxley, J. G.On connectivity in matroids and graphs. Trans. Amer. Math. Soc. (to appear).Google Scholar
(8)Richardson, W. R. H. Decomposition of chain-groups and binary matroids. Proc. Fourth South-Eastern Conf. on Combinatorics, Graph Theory, and Computing (Utilitas Mathe-matica, Winnipeg, 1973), 463476.Google Scholar
(9)Seymour, P. D.Matroid representation over GF(3). J. Combin. Theory B 26 (1979), 159173.Google Scholar
(10)Seymour, P. D.Packing and covering with matroid circuits. J. Combin. Theory B 28 (1980), 237242.Google Scholar
(11)Tutte, W. T.A theory of 3-connected graphs. Nederl. Akad. Wetensch. Proc. Ser. A 64 (1961), 441455.CrossRefGoogle Scholar
(12)Tutte, W. T.Connectivity in matroids. Canad. J. Math. 18 (1966), 13011324.Google Scholar
(13)Tutte, W. T. Connectivity in matroids. Graph theory and its applications, ed. Harris, B. (Academic Press, New York, 1970), 113119.Google Scholar
(14)Welsh, D. J. A.Matroid theory, London Math. Soc. Monographs no. 8 (Academic Press, London, New York, San Francisco, 1976).Google Scholar