Article in volume
Authors:
Title:
Set-sequential labelings of odd trees
PDFSource:
Discussiones Mathematicae Graph Theory 44(1) (2024) 151-170
Received: 2020-12-17 , Revised: 2021-11-06 , Accepted: 2021-11-07 , Available online: 2021-11-22 , https://doi.org/10.7151/dmgt.2439
Abstract:
A tree \(T\) on \(2^n\) vertices is called set-sequential if the elements
in \(V(T)\cup 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 \(\mathbb{F}_2^n\) in a particular way; in the process, we provide a
substantial clarification of a proof of a theorem that partitions
\(\mathbb{F}_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.
Keywords:
trees, coloring graphs by sets, caterpillars
References:
- B.D. Acharya and S.M. Hegde, Set sequential graphs, Nat. Acad. Sci. Lett. 8 (1985) 387–390.
- K. Abhishek, Set-valued graphs II, J. Fuzzy Set Valued Anal. 2013 (2013) 1–16.
- K. Abhishek and G.K. Agustine, Set-valued graphs, J. Fuzzy Set Valued Anal. 2012 (2012) 1–17.
- P.N. Balister, E. Győri and R.H. Schelp, Coloring vertices and edges of a graph by nonempty subsets of a set, European J. Combin. 32 (2011) 533–537.
https://doi.org/10.1016/j.ejc.2010.11.008 - L. Golowich and C. Kim, New classes of set-sequential trees, Discrete Math. 343 (2020) 111741.
https://doi.org/10.1016/j.disc.2019.111741 - S.M. Hegde, Set colorings of graphs, European J. Combin. 30 (2009) 986–995.
https://doi.org/10.1016/j.ejc.2008.06.005 - A.R. Mehta, G.R. Vijayakumar and S. Arumugam, A note on ternary sequences of strings of $0$ and $1$, AKCE Int. J. Graphs Comb. 5 (2008) 175–179.
https://doi.org/10.1080/09728600.2008.12088862
Close