Multiset Dimensions of Trees

arXiv1908.05879MaRDI QIDQ6323752FDOQ6323752

Rizki Kurniawan, Yusuf Hafidh, Steven Tanujaya, Suhadi Wido Saputro, Rinovia Simanjuntak, S. Uttunggadewa

Publication date: 16 August 2019

Abstract: 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$, $r_m(v|W)$, is defined as a multiset of distances between $v$ and the vertices in $W$. If $r_m(u|W)eq{r}_m(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)=infty$. In this paper, we show that for a tree $T$ of diameter at least 2, if $md(T)<infty$, then $md(T)leqn-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].

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12)

This page was built for publication: Multiset Dimensions of Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6323752)