Hostname: page-component-669899f699-b58lm Total loading time: 0 Render date: 2025-04-26T08:36:41.623Z Has data issue: false hasContentIssue false
  • English
  • Français

On maximum matchings in cubic graphs with a bounded number of bridge-covering paths

Published online by Cambridge University Press:  17 April 2009

Gary Chartrand ,
S.F. Kapoor ,
Ortrud R. Oellermann  and
Sergio Ruiz
Gary Chartrand
Affiliation:
Department of Maths and Statistics, Western Michigan University, KALAMAZOO, MI 49008 – 3899, U.S.A.
S.F. Kapoor
Affiliation:
Department of Maths and Statistics, Western Michigan University, KALAMAZOO, MI 49008 – 3899, U.S.A.
Ortrud R. Oellermann
Affiliation:
Department of Maths and Statistics, Western Michigan University, KALAMAZOO, MI 49008 – 3899, U.S.A.
Sergio Ruiz
Affiliation:
Instituto de Matematicas, Universidad Catolica de Valpararaiso, Chile.
Rights & Permissions [Opens in a new window]

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
[3]Errera, A., “Du colorage des cartes”, Mathesis 36 (1922), 56–60.Google Scholar
[4]Petersen, J., “Die theorie der regulären graphen”, Acta Math. 15 (1891), 163–220.Google Scholar
[5]Tutte, W.T., “The factorizations of linear graphs”, J. London Math. Soc. 22 (1947), 107–111.CrossRefGoogle Scholar