Abstract
New classes of explicit matchings for the bipartite graph ℬ(k) consisting of the middle two levels of the Boolean lattice on 2k+1 elements are constructed and counted. This research is part of an ongoing effort to show that ℬ(k) is Hamiltonian.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
I. J. Dejter (1985) Hamiltonian cycles and quotients of bipartite graphs, in Graph Theory and Applications to Algorithms and Computer Science (eds. Y. Alavi et al.) John Wiley, New York, pp. 189–199.
I. J. Dejter, Hamiltonian cycles in bipartite reflective Kneser graphs, preprint.
D. Duffus, P. Hanlon, and R. Roth, Matchings and Hamiltonian cycles in some families of symmetric graphs, Nokahoma Math. J., to appear.
D. Duffus, B. Sands, and R. Woodrow (1988) Lexicographical matchings cannot form Hamiltonian cycles, Order 5, 149–161.
W. Feller, An Introduction to Probability and Its Applications 1, 3rd edn.
I. Havel (1983) Semipaths in directed cubes, in Graphs and Other Combinatorial Topics, M. Fiedler (ed.) Teubner, Leipzig, pp. 101–108.
C. Little, D. Grant, and D. Holton (1975) On defect-d matchings in graphs, Discrete Math. 13, 41–54.
T. Narayana (1979) Lattice Path Combinatorics with Statistical Applications, Math. Expositions 23, University of Toronto Press.
Author information
Authors and Affiliations
Additional information
Communicated by D. Duffus
Supported by Office of Naval Research contract N00014-85K-0494.
Supported by National Science Foundation grant DMS-8041281.
Rights and permissions
About this article
Cite this article
Kierstead, H.A., Trotter, W.T. Explicit matchings in the middle levels of the Boolean lattice. Order 5, 163–171 (1988). https://doi.org/10.1007/BF00337621
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF00337621