Corrigendum and addendum to: “Pseudo-matchings of a bipartite graph” (Proc. Amer. Math. Soc. 42 (1974), 28–32) by Alan Brace and Daykin

Daykin, D. E.

doi:10.1090/S0002-9939-1976-0409269-7

Corrigendum and addendum to: “Pseudo-matchings of a bipartite graph” (Proc. Amer. Math. Soc. 42 (1974), 28–32) by Alan Brace and Daykin
HTML articles powered by AMS MathViewer

by D. E. Daykin PDF

Proc. Amer. Math. Soc. 56 (1976), 380-382 Request permission

Abstract:

For an undirected bipartite graph $G$ conditions on $\deg x + \deg y$ for $xy \notin G$ ensure sets of independent lines extend to hamiltonian cycles.

References

Claude Berge, Théorie des graphes et ses applications, Collection Universitaire de Mathématiques, II, Dunod, Paris, 1958 (French). MR 0102822
J. A. Bondy, Trigraphs, Discrete Math. 75 (1989), no. 1-3, 69–79. Graph theory and combinatorics (Cambridge, 1988). MR 1001387, DOI 10.1016/0012-365X(89)90079-4
Alan Brace and D. E. Daykin, Pseudo-matchings of a bipartite graph, Proc. Amer. Math. Soc. 42 (1974), 28–32. MR 329960, DOI 10.1090/S0002-9939-1974-0329960-9
Hudson V. Kronk, Variations on a theorem of Pósa, The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) Springer, Berlin, 1969, pp. 193–197. MR 0255437
M. Meyniel, Une condition suffisante d’existence d’un circuit Hamiltonien dans un graphe oriente, J. Combinatorial Theory Ser. B 14 (1973), 137–147 (French). MR 317997, DOI 10.1016/0095-8956(73)90057-9
J. Moon and L. Moser, On Hamiltonian bipartite graphs, Israel J. Math. 1 (1963), 163–165. MR 161332, DOI 10.1007/BF02759704
D. R. Woodall, Sufficient conditions for circuits in graphs, Proc. London Math. Soc. (3) 24 (1972), 739–755. MR 318000, DOI 10.1112/plms/s3-24.4.739