Graph Labelings in Boolean Lattices

Abstract

A graph $G$ is said to be embeddable in a set $X$ if there exists a mapping $f$ from $E(G)$ to the set $\mathcal{P}(X)$ of all subsets of $X$ such that if we define a mapping $g$ from $V(G)$ to $\mathcal{P}(X)$ by letting $g(x)$ be the union of $f(e)$ as $e$ ranges over all edges incident with $x$, then $g$ is injective. We show that for each integer $k\ge 2$, every graph of order at most $2^k$ all of whose components have order at least $3$ is embeddable in a set of cardinality $k$.