Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Pseudo-matchings of a bipartite graph

Authors: Alan Brace and D. E. Daykin
Journal: Proc. Amer. Math. Soc. 42 (1974), 28-32
MSC: Primary 05C35
Corrigendum: Proc. Amer. Math. Soc. 56 (1976), 380-382.
MathSciNet review: 0329960
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let G be a graph whose edges (x, y) have $ x \in X,y \in Y,\vert X\vert = \vert Y\vert < \infty $ . A (t, u) cover of G is a set of t edges which cover $ \geqq u$ vertices in both X and Y. We give conditions on the valency (minimum local degree) and the number of edges which ensure a (t, u) cover or that a Hamiltonian circuit exists.

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

  • [1] Alan Brace, Some combinatorial cover theorems, Ph.D. Thesis, University of Western Australia, 1971.
  • [2] C. Berge, Théorie des graphes et ses applications, Collection Univ. Math., II, Dunod, Paris, 1958; English transl., Methuen, London; Wiley, New York, 1962. MR 21 #1608; 24 #A2381. MR 0102822 (21:1608)
  • [3] D. R. Woodall, Sufficient conditions for circuits in graphs, Proc. London Math. Soc. (3) 24 (1972), 739-755. MR 0318000 (47:6549)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05C35

Retrieve articles in all journals with MSC: 05C35

Additional Information

Keywords: Circuit, graph, Hall theorem, Hamiltonian, König, matching, number of edges, Ore, valency
Article copyright: © Copyright 1974 American Mathematical Society

American Mathematical Society