Abstract
In this paper we extensively treat the following problems: When is a given graph a subgraph (resp. induced subgraph) of a hypercube and when is an ordered set a subdiagram (resp. induced subdiagram) of a Boolean lattice? We present characterizations for that in terms of suitable edge-colorings of the graphs and, for ordered sets, of their covering graphs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Burosh, G. and Laborde, J. (1992) Einbettungen von Graphen in den n-Würfel, in K. Wagner and R. Bodendiek (eds), Graphentheorie III, pp. 73–94.
GareyM. R. and GrahamR. L. (1975) On cubical graphs, Journal of Combinatorial Theory B 18, 84–95.
HararyF., HayesJ. P. and WuHorng-Jyh (1988) A survey of the theory of hypercube graphs, Comput. Math. Applic. 15(4), 277–289.
HavelI. and MovárekJ. (1972) B-valuation of graphs, Czech. Math. Journal 22, 338–351.
Krumme, D. W., Venkataraman, K. N. and Cybenko, G. (1986) Hypercube embedding is NP-complete, in M. T. Heath (ed.), Proceedings of the 1st Conference on Hypercube Multiprocessors, SIAM, Philadelphia, PA, pp. 148–157.
Mitas, J. and Reuter, K. (1995) Cover-preserving embeddings of bipartite orders into Boolean lattices, Theoret. Comp. Sci., accepted for publication.
WagnerA. and CorneilD. G. (1990) Embedding trees in a hypercube is NP-complete, SIAM J. Comput 19(4), 570–590.
WildMarcel (1992) Cover-preserving order embeddings into Boolean lattices, Order 9, 209–232.
Author information
Authors and Affiliations
Additional information
Communicated by I. Rival
The first author acknowledges the support by the Deutsche Forschungsgemeinschaft.
Rights and permissions
About this article
Cite this article
Mitas, J., Reuter, K. Subgraphs of hypercubes and subdiagrams of boolean lattices. Order 13, 41–64 (1996). https://doi.org/10.1007/BF00383967
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF00383967