No label defined (Q4940037)

The graph of an \(n\)-cube is denoted by \(Q_n\). If \(E\subseteq E(Q_n)\) and \(G\) is a subgroup of \(\Aut(Q_n)\) such that \(\{g(E)\mid g\in G\}\) is an edge decomposition of \(Q_n\), then \(E\) is said to be a fundamental set for \(Q_n\) with group \(G\). \(E\) is called fundamental set if such a subgroup \(G\) exists. The author studies subsets \(E\) of \(E(Q_n)\) fulfilling \(|E|=2n\) with the aim of discovering which are fundamental sets. The second point of interest is the question which graphs \(\Gamma \) (and especially, which trees) with \(2n\) edges have embeddings \(\varphi \) in \(Q_n\) such that \(E(\varphi (\Gamma))\) is a fundamental set for \(Q_n\). Such a \(\varphi \) is called a fundamental embedding. Trying to obtain fundamental embeddings the author uses the concept of the so-called 2-1-labelling \(\lambda :E(\Gamma)\to \{1,2,\dots ,n\}\) of a tree \(\Gamma \). This is a 2-1-mapping fulfilling the condition that on each path \(P'\) in \(\Gamma \) some edge label occurs an odd number of times. Fixing any vertex of \(V(\Gamma)\) and mapping it to the null vertex of \(Q_n\) one obviously obtains an embedding of \(\Gamma \) in \(Q_n\), called a 2-1-embedding. (The resulting subgraph of \(Q_n\) has exactly 2 edges in each direction.) Examples of results are: characterization of the trees on \(2n\) edges which can be embedded in \(Q_n\), characterization of those which have 2-1-embedding, and characterization of the trees of diameter 4 with a 2-1-labelling which yields a fundamental set. The question was asked whether there is a path on \(2n\) edges in \(Q_n\) which is a fundamental set. The author shows that for \(n\) odd the answer is ``no'', he presents an example of such a path for \(n=4\) and conjectures that such paths exist for \(n\) even, \(n\geq 4\).