1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Set-Sequential Labelings of Odd Trees

Published Online: 26 Nov 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 17 Dec 2020
Accepted: 07 Nov 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

A tree T on 2n 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 2n 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 𝔽2n \mathbb{F}_2^n in a particular way; in the process, we provide a substantial clarification of a proof of a theorem that partitions 𝔽2n \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

MSC 2010

[1] B.D. Acharya and S.M. Hegde, Set sequential graphs, Nat. Acad. Sci. Lett. 8 (1985) 387–390. Search in Google Scholar

[2] K. Abhishek, Set-valued graphs II, J. Fuzzy Set Valued Anal. 2013 (2013) 1–16.10.5899/2013/jfsva-00149 Search in Google Scholar

[3] K. Abhishek and G.K. Agustine, Set-valued graphs, J. Fuzzy Set Valued Anal. 2012 (2012) 1–17.10.5899/2012/jfsva-00127 Search in Google Scholar

[4] 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.00810.1016/j.ejc.2010.11.008 Search in Google Scholar

[5] L. Golowich and C. Kim, New classes of set-sequential trees, Discrete Math. 343 (2020) 111741. https://doi.org/10.1016/j.disc.2019.11174110.1016/j.disc.2019.111741 Search in Google Scholar

[6] S.M. Hegde, Set colorings of graphs, European J. Combin. 30 (2009) 986–995. https://doi.org/10.1016/j.ejc.2008.06.00510.1016/j.ejc.2008.06.005 Search in Google Scholar

[7] 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 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo