New Classes of Set-Sequential Trees

Abstract

A graph is called set-sequential if its vertices can be labeled with distinct nonzero vectors in ${\mathbb{F}}_2^n$ such that when each edge is labeled with the sum$(\mathrm{mod}2)$ of its vertices, every nonzero vector in ${\mathbb{F}}_2^n$ is the label for either a single vertex or a single edge. We resolve certain cases of a conjecture of Balister, Gyori, and Schelp in order to show many new classes of trees to be set-sequential. We show that all caterpillars $T$ of diameter $k$ such that $k\le 18$ or $|V(T)|\ge 2^{k-1}$ are set-sequential, where $T$ has only odd-degree vertices and $|T|=2^{n-1}$ for some positive integer $n$. We also present a new method of recursively constructing set-sequential trees.

19 pages, 1 figure