Set-sequential labelings of odd trees (Q6985945)

The authors study set-sequential graphs, where vertices and edges are labeled with distinct nonzero binary vectors such that each edge's label equals the sum of its endpoints' labels \(\pmod 2\). They mostly focus on the odd tree conjecture, which states that every tree with \(2^n\) vertices, all of them having odd degree, is set-sequential.\N\NThe authors confirm the conjecture for small trees (\(n\leq 3\)) and caterpillars with \(n\geq 2\), \(n\neq 4\) and all the degrees in \(\{1,3\}\). They also introduce special constructions and show how to build larger set-sequential trees by splicing smaller ones.\N\NThey also present methods for combining bipartite graphs with caterpillars, preserving the desired property under some conditions. An important part of the paper involves vector pairing conjectures in \(\mathbb{F}_2^n\), including cases where vectors sum up to zero or follow specific patterns of repetitions. These part of the paper supports the construction of other set-sequential trees.\N\NThe full odd tree conjecture remains open; however, the results presented in the paper make significant progress in proving it and suggest interesting directions for further research.