z-logo
open-access-imgOpen Access
On the dimension of vertex labeling of $k$-uniform dcsl of $k$-uniform caterpillar
Author(s) -
K. Nageswara Rao,
K. A. Germina,
P. Shaini
Publication year - 2016
Publication title -
carpathian mathematical publications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.63
H-Index - 4
eISSN - 2313-0210
pISSN - 2075-9827
DOI - 10.15330/cmp.8.1.134-149
Subject(s) - combinatorics , mathematics , injective function , vertex (graph theory) , order (exchange) , dimension (graph theory) , graph , integer (computer science) , linear extension , partially ordered set , discrete mathematics , finance , computer science , economics , programming language
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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom