Set-sequential labelings of odd trees

Eckels, Emily  ; Győri, Ervin ; Liu, Junsheng ; Nasir, Sohaib

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 151-170

Résumé

A tree T on 2^n vertices is called set-sequential if the elements in V(T)∪ E(T) can be labeled with distinct nonzero (n+1)-dimensional 01-vectors such that the vector labeling each edge is the component-wise sum modulo 2 of the labels of the endpoints. It has been conjectured that all trees on 2^n vertices with only odd degree are set-sequential (the “Odd Tree Conjecture”), and in this paper, we present progress toward that conjecture. We show that certain kinds of caterpillars (with restrictions on the degrees of the vertices, but no restrictions on the diameter) are set-sequential. Additionally, we introduce some constructions of new set-sequential graphs from smaller set-sequential bipartite graphs (not necessarily odd trees). We also make a conjecture about pairings of the elements of 𝔽_2^n in a particular way; in the process, we provide a substantial clarification of a proof of a theorem that partitions 𝔽_2^n from a paper [Coloring vertices and edges of a graph by nonempty subsets of a set, European J. Combin. 32 (2011) 533–537] by Balister et al. Finally, we put forward a result on bipartite graphs that is a modification of a theorem in the aforementioned paper.

Détail

Keywords: trees, coloring graphs by sets, caterpillars