On $\alpha$-Valuations of Disconnected Graphs

Abstract

We introduce the concept of a free $a$-valuation of a graph, and prove that the vertex-disjoint union of any collection of graphs with free $\alpha$-valuations has an $\alpha$-valuation. Many bipartite graphs have free $\alpha$-valuations, including the complete bipartite graph $K_{m,n}$ when $m>1$ and $n>2$, and the $d$-cube $Q_d$ for $d>2$.