On the dimension of vertex labeling of $k$-uniform dcsl of $k$-uniform caterpillar

Abstract

A distance compatible set labeling (dcsl) of a connected graph $G$ is an injective set assignment $f : V(G) \rightarrow 2^{X},$ $X$ being a nonempty ground set, such that the corresponding induced function $f^{\oplus} :E(G) \rightarrow 2^{X}\setminus \{\emptyset\}$ given by $f^{\oplus}(uv)= f(u)\oplus f(v)$ satisfies $\mid f^{\oplus}(uv) \mid = k_{(u,v)}^{f}d_{G}(u,v)$ for every pair of distinct vertices $u, v \in V(G),$ where $d_{G}(u,v)$ denotes the path distance between $u$ and $v$ and $k_{(u,v)}^{f}$ is a constant, not necessarily an integer. A dcsl $f$ of $G$ is $k$-uniform if all the constant of proportionality with respect to $f$ are equal to $k,$ and if $G$ admits such a dcsl then $G$ is called a $k$-uniform dcsl graph. The $k$-uniform dcsl index of a graph $G,$ denoted by $\delta_{k}(G)$ is the minimum of the cardinalities of $X,$ as $X$ varies over all $k$-uniform dcsl-sets of $G.$ A linear extension ${\mathbf{L}}$ of a partial order ${\mathbf{P}} = (P, \preceq)$ is a linear order on the elements of $P$, such that $x \preceq y$ in ${\mathbf{P}}$ implies $x \preceq y$ in ${\mathbf{L}}$, for all $x, y \in P$. The dimension of a poset ${\mathbf{P}},$ denoted by $dim({\mathbf{P}}),$ is the minimum number of linear extensions on ${\mathbf{P}}$ whose intersection is `$\preceq$'. In this paper we prove that $dim({\mathcal{F}}) \leq \delta_{k}(P^{+k}_n),$ where ${\mathcal{F}}$ is the range of a $k$-uniform dcsl of the $k$-uniform caterpillar, denoted by $P^{+k}_n \ (n\geq 1, k\geq 1)$ on `$n(k+1)$' vertices.