2019/08/16 by Yusuf Hafidh, Hafidh, Yusuf, Rizki Kurniawan +9
Computer Science · Engineering · Medicine · #05C05 #05C12 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Synthesis of Organic Compounds #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1908.05879
openalex publication_date 2019/08/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a connected graph and W be a set of vertices of G. The representation multiset of a vertex v with respect to W, rm (v|W), is defined as a multiset of distances between v and the vertices in W. If rm (u |W) ≠ rm(v|W) for every pair of distinct vertices u and v, then W is called an m-resolving set of G. If G has an m-resolving set, then the cardinality of a smallest m-resolving set is called the multiset dimension of G, denoted by md(G); otherwise, we say that md(G) = ∞. In this paper, we show that for a tree T of diameter at least 2, if md(T) < ∞, then md(T) ≤ n-2. We conjecture that this bound is not sharp in general and propose a sharp upper bound. We shall also provide necessary and sufficient conditions for caterpillars and lobsters having finite multiset dimension. Our results partially settled a conjecture and an open problem proposed in [4].