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

Abstract

Нехай сумісна з відстанями множина позначень (dcsl) зв'язаного графа G є ін'єктивною множиною відновіних присвоєнь f:V(G)2X X -- непорожня базова множина така, що відповідна індукована функція f:E(G)2X задана як f(uv)=f(u)f(v) задовільняє умову f(uv)=kf(uv)dG(uv) для кожної пари різнорідних вершин uvV(G) де dG(uv) позначає пройдену відстань між u і v, та kf(uv) не обов'язково ціла константа, що залежить від пари обраних вершин uv. G є графом з сумісною з відстанями множиною позначень (dcsl графом), якщо він дозволяє dcsl. Множина dcsl f для (pq)-графа G є розсіюваною, якщо сталі пропорційності kf(uv) відносно fu=vuv V(G) є значущими і G є розсіюваним, якщо він доспускає dcsl розсіювання. У цій статті доведено, що всі шляхи і графи з діаметром не більшим 2 є розсіюваними.