Decompositions of complete graphs into isomorphic bipartite subgraphs (Q1323486)

Let \(f\) be a 1-1 mapping of \(V(G)\) into the set \(S= \{0,1,\dots,| E(G)|\}\). Then \(f\) is called a \(\beta\)-valuation of \(G\) if the induced function \(\overline f: E(G)\to S\) given by \(\overline f(uv)= | f(u)- f(v)|\), for all \(uv\in E(G)\), is 1-1. A \(\beta\)-valuation \(f\) is called \(\alpha\)-valuation of \(G\) if there exists a nonnegative number \(\lambda\) such that for every \(uv\in E(G)\) with \(f(u)< f(v)\) we have \(f(u)< \lambda< f(v)\). Let \(Q_ n(G)= G\times K_ 2\times\cdots\times K_ 2= G\times (K_ 2)^{n-1}\) denote the graph of the \(n\)-dimensional \(G\)-cube. The authors prove that for any positive integer \(n\) and \(G= K_{3,3}\), \(K_{4,4}\) and \(P_ k\) the graph \(Q_ n(G)\) has an \(\alpha\)-valuation. This result together with Rosa's theorem guarantees the decomposition of some complete graphs into certain bipartite graphs.