Деякі класи розсіюваних dcsl графів

Анотація

Нехай сумісна з відстанями множина позначень (dcsl) зв'язаного графа $G$ є ін'єктивною множиною відновіних присвоєнь $f : V(G) \rightarrow 2^{X},$ $X$ -- непорожня базова множина така, що відповідна індукована функція $f^{\oplus} :E(G) \rightarrow 2^{X}\setminus \{\phi\}$ задана як $f^{\oplus}(uv)= f(u)\oplus f(v)$ задовільняє умову $|f^{\oplus}(uv)| = k_{(u,v)}^{f}d_{G}(u,v)$ для кожної пари різнорідних вершин $u, v \in V(G),$ де $d_{G}(u,v)$ позначає пройдену відстань між $u$ і $v$, та $k_{(u,v)}^{f}$ не обов'язково ціла константа, що залежить від пари обраних вершин $u,v$. $G$ є графом з сумісною з відстанями множиною позначень (dcsl графом), якщо він дозволяє dcsl. Множина dcsl $f$ для $(p, q)$-графа $G$  є розсіюваною, якщо сталі пропорційності $k^f_{(u,v)}$ відносно $f, u \neq v, u, v \in  V(G)$ є значущими і $G$ є розсіюваним, якщо він доспускає dcsl розсіювання. У цій статті доведено, що всі шляхи і графи з діаметром не більшим $2$ є розсіюваними.