Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
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 (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

DOI: http://dx.doi.org/10.1090/S0002-9939-1974-0329960-9
PII: S 0002-9939(1974)0329960-9
Keywords: Circuit, graph, Hall theorem, Hamiltonian, König, matching, number of edges, Ore, valency
Article copyright: © Copyright 1974 American Mathematical Society