On subset labelings of trees
AbstractFor a nontrivial graph G, a subset labeling of G is a labeling of the vertices of G with nonempty subsets of the set [Formula: see text] for a positive integer r such that two vertices of G have disjoint labels if and only if the vertices are adjacent. The subset index [Formula: see text] of...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2024-01-01
|
| Series: | AKCE International Journal of Graphs and Combinatorics |
| Subjects: | |
| Online Access: | https://www.tandfonline.com/doi/10.1080/09728600.2023.2254562 |
| Summary: | AbstractFor a nontrivial graph G, a subset labeling of G is a labeling of the vertices of G with nonempty subsets of the set [Formula: see text] for a positive integer r such that two vertices of G have disjoint labels if and only if the vertices are adjacent. The subset index [Formula: see text] of G is the minimum positive integer r for which G has such a subset labeling from the set [Formula: see text]. If T is a tree of diameter d, then [Formula: see text]. It is shown that there are several classes of trees T of diameter d such that [Formula: see text] and for every pair a, b of integers with [Formula: see text], there is a tree T of diameter d such that [Formula: see text] and [Formula: see text]. Sharp bounds are established for the subset indices of the starlike trees [Formula: see text] obtained by subdividing each edge of the star [Formula: see text]a total of r times. Other results and open questions are also presented on subset indices of trees. |
|---|---|
| ISSN: | 0972-8600 2543-3474 |