Про розмірність маркування вершин $k$-однорідного dcsl $k$-однорідного графа

Анотація

Сумісне з відстанню множинне маркування (dcsl) зв’язного графа $G$ є ін’єктивним відображенням $f : V(G) \rightarrow 2^{X},$ де $X$ є непорожною базовою множиною такою, що відповідна індукована функція $f^{\oplus} :E(G) \rightarrow 2^{X}\setminus \{\emptyset\}$, задана рівністю $f^{\oplus}(uv)= f(u)\oplus f(v)$, задовольняє $\mid f^{\oplus}(uv) \mid = k_{(u,v)}^{f}d_{G}(u,v)$ для довільної пари різних вершин $u, v\in V(G),$ де $d_{G}(u,v)$ позначає відстань між $u$ і $v$ та $k_{(u,v)}^{f}$ є числом, не обов’язково цілим. Сумісне з відстанню множинне маркування $f$ графа $G$ є $k$-однорідним, якщо всі коефіцієнти пропорційності  відносно $f$ рівні $k,$ і якщо $G$ допускає таке маркування, то $G$ називають $k$-однорідним dcsl графом. \textit{$k$-однорідний dcsl індекс} графа $G,$ що позначається $\delta_{k}(G)$, є мінімальним серед потужностей $X,$ де $X$ пробігає всі $k$-однорідні dcsl-множини графа $G.$ \textit{Лінійне розширення} ${\mathbf{L}}$ часткового порядку  ${\mathbf{P}} = (P, \preceq)$ є лінійним порядком на елементах із $P$ таким, що з $x \preceq y$ в ${\mathbf{P}}$ слідує, що $x \preceq y$ в ${\mathbf{L}}$ для всіх $x, y \in P$. Розмірність множини ${\mathbf{P}},$ яка позначається $dim({\mathbf{P}}),$ є мінімальним числом лінійних розширень на ${\mathbf{P}}$, перетин яких є `$\preceq$'. У цій статті ми доводимо, що $dim({\mathcal{F}}) \leq \delta_{k}(P^{+k}_n),$ де ${\mathcal{F}}$ є образом $k$-однорідного dcsl $k$-однорідного графа, позначеного $P^{+k}_n \ (n\geq 1, k\geq 1)$ на `$n(k+1)$' вершинах.