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 Free Access

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] Claude Berge, Théorie des graphes et ses applications, Collection Universitaire de Mathématiques, II, Dunod, Paris, 1958 (French). MR 0102822
  • [3] D. R. Woodall, Sufficient conditions for circuits in graphs, Proc. London Math. Soc. (3) 24 (1972), 739–755. MR 0318000

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