No CrossRef data available.
Article contents
On maximum matchings in cubic graphs with a bounded number of bridge-covering paths
Published online by Cambridge University Press: 17 April 2009
Extract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.
It is proved that if G is a connected cubic graph of order p all of whose bridges lie on r edge-disjoint paths of G, then every maximum matching of G contains at least P/2 − └2r/3┘ edges. Moreover, this result is shown to be best possible.
- Type
- Research Article
- Information
- Bulletin of the Australian Mathematical Society , Volume 36 , Issue 3 , December 1987 , pp. 441 - 447
- Copyright
- Copyright © Australian Mathematical Society 1987
References
[1]Berge, C., “Two theorems in graph theory”, Proc. Nat. Acad. Sci. 43 (1957), 842–844.CrossRefGoogle ScholarPubMed
[2]Chartrand, G., Kapoor, S.F., Lesniak, L. and Schuster, S., “Near l-factors in graphs”, Proceedings of the Fourteenth Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium 41 (1984), 131–147.Google Scholar
[5]Tutte, W.T., “The factorizations of linear graphs”, J. London Math. Soc. 22 (1947), 107–111.CrossRefGoogle Scholar