Roma dominantlığı qrafın təpələrinə müdafiə resursu kimi şərh edilə bilən tam ədəd etiketləri verib bütün təpələrin müəyyən qonşuluq şərtləri altında qorunmasını təmin edərkən etiketlərin ümumi çəkisini minimuma endirməyi hədəfləyən qraf optimallaşdırma modelidir. Juan Carlos Valenzuela-Tripodoro, María Antonia Mateos-Camacho, Martín Cera López və María Pilar Álvarez-Ruíz-in işi bu modelin iki inkişaf etmiş formasını — [k]-Roma dominantlığını və güclü Roma dominantlığını — həm hesablama mürəkkəbliyi, həm də müəyyən qraf ailələrində dəqiq parametr qiymətləri baxımından araşdırır.

[k]-Roma dominantlığı tərəfdə müəlliflər problemi Linear Extended Monadic Second-Order Logic (LinEMSOL) formasında ifadə edirlər. Bunun nəticəsi olaraq uyğun qraf təqdimatı mövcud olduqda məhdud clique-width siniflərində problem qrafın mərtəbəsinə görə xətti zamanda həll edilə bilir. Güclü Roma dominantlığı tərəfdə isə qərar probleminin ulduz-konveks iki hissəli qraflarda NP-tam olduğu Restricted Exact 3-Cover problemindən qurulan reduksiya ilə göstərilir.

İşin ikinci əsas istiqaməti dəqiq qiymətlərdir. İkiqat ulduzlar, müəyyən yollar və dövrlər, t-qatlı çarxlar, tac qrafları, dövr ilə tək təpənin korona hasili və müəyyən tırtıl qraf sinifləri üçün [k]-Roma və ya güclü Roma dominantlıq ədədləri müəyyən edilir. Nəticələr eksperimental deyil; qraf etiketləmələri, kombinatorik aşağı və yuxarı sərhədlər, məntiqi ifadə edilə bilmə, mürəkkəblik reduksiyaları və konstruktiv isbatlara əsaslanır.

Roma dominantlığı nədir?

Roma dominantlığı qrafın təpələrinə 0, 1 və ya 2 etiketlərini verən və 0 etiketli hər təpənin ən azı bir 2 etiketli qonşuya malik olmasını tələb edən təpə-etiketləmə optimallaşdırma modelidir; məqsəd bütün etiketlərin ümumi çəkisini minimuma endirməkdir.

Sadə, istiqamətsiz və sonlu qraf

\[ G=(V,E) \]

ilə göstərilsin. Burada \(V\) təpələr çoxluğunu, \(E\) isə kənarlar çoxluğunu ifadə edir. Klassik Roma dominantlıq funksiyası

\[ f:V\rightarrow\{0,1,2\} \]

şəklindədir. Əgər \(f(v)=0\) olarsa, \(v\)-nin ən azı bir qonşusu \(u\) üçün

\[ f(u)=2 \]

olmalıdır.

Funksiyanın çəkisi

\[ w(f)=\sum_{v\in V}f(v) \]

şəklindədir. Qrafın Roma dominantlıq ədədi

\[ \gamma_R(G) \]

isə bütün etibarlı Roma dominantlıq funksiyaları arasındakı ən kiçik çəkidir.

“Roma” adı tarixi müdafiə bənzətməsindən gəlir: 0 etiketli mövqedə birbaşa müdafiə vahidi yoxdur; lakin qonşu mövqedə iki vahid varsa, həmin qonşu öz müdafiəsini tam itirmədən bir vahidi köməyə göndərə bilər. Riyazi baxımdan vacib olan tarixi hekayə deyil, qraf üzərində lokal qoruma şərtləri ilə ümumi resurs xərcinin birlikdə optimallaşdırılmasıdır.

Qonşuluq və aktiv qonşuluq

Bir \(u\) təpəsinin açıq qonşuluğu \(N(u)\), \(u\)-ya bitişik təpələrin çoxluğudur. Qapalı qonşuluq isə

\[ N[u]=N(u)\cup\{u\} \]

kimi müəyyən edilir.

Bir etiketləmə \(f\) verildikdə aktiv qonşuluq

\[ AN(u)=\{w\in N(u):f(w)>0\} \]

çoxluğudur. Bu anlayış xüsusilə [k]-Roma dominantlığının tərifində mərkəzi rol oynayır.

[k]-Roma dominantlığı klassik modeldən necə fərqlənir?

\[k]-Roma dominantlığı hər təpəyə \(0\) ilə \(k+1\) arasında etiket verilməsinə imkan verir və hər təpənin qapalı qonşuluğundakı ümumi etiket çəkisinin ən azı \(k\) üstəgəl aktiv qonşuların sayı qədər olmasını tələb etməklə klassik Roma dominantlığını daha ümumi resurs-bölüşdürmə modelinə çevirir.

Bir [k]-Roma dominantlıq funksiyası, qısaca [k]-RDF,

\[ f:V\rightarrow\{0,1,\ldots,k+1\} \\]

şəklində müəyyən edilir və hər \(u\in V\) üçün

\[ f(N[u])\geq k+|AN(u)| \]

şərtini ödəməlidir.

Burada

\[ f(N[u])=\sum_{v\in N[u]}f(v) \]

qapalı qonşuluqdakı etiketlərin cəmidir. \(|AN(u)|\), \(u\)-nun müsbət etiket daşıyan aktiv qonşularının sayıdır. Buna görə tələb olunan minimum cəm yalnız \(k\)-dan deyil, eyni zamanda həmin təpənin ətrafında neçə aktiv təpənin olduğundan da asılıdır.

Qraf üzərində minimum [k]-Roma dominantlıq çəkisi

\[ \gamma_{[kR]}(G) \]

ilə göstərilir.

Mənbənin Şəkil 1-i eyni qraf üzərində klassik Roma dominantlıq etiketləməsi ilə [k]-Roma etiketləməsini yanaşı göstərir. Nümunədə klassik qiymət

\[ \gamma_R(G)=6 \]

ikən göstərilən [k]-Roma qiyməti

\[ \gamma_{[kR]}(G)=3(k+1) \]

şəklindədir. Bunlar bütün qraflar üçün ümumi düsturlar deyil, Şəkil 1-dəki konkret qrafın etiketləmələrini izah edən qiymətlərdir.

Güclü Roma dominantlığı nəyi modelləşdirir?

Güclü Roma dominantlığı tək bir hücum əvəzinə eyni anda bir neçə müdafiəsiz qonşunun qoruna bilməsini modelləşdirmək üçün müsbət etiket daşıyan güclü təpənin 0 etiketli qonşularının ən azı yarısına yetəcək müdafiə çəkisi daşımasını tələb edən Roma dominantlığı variantıdır.

Qrafın maksimum dərəcəsi \(\Delta\) olsun. Güclü Roma dominantlıq funksiyası, qısaca StRDF, təpələri

\[ \left\{0,1,2,\ldots,\left\lceil\frac{\Delta}{2}\right\rceil+1\right\} \]

çoxluğundan etiketləyir.

\[ B_0=\{w\in V:f(w)=0\} \]

0 etiketli təpələr çoxluğu olmaqla, hər \(v\in B_0\) üçün bir qonşu \(u\) tapılmalı və

\[ f(u)\geq 1+ \left\lceil \frac{|N(u)\cap B_0|}{2} \right\rceil \]

şərti ödənməlidir.

Bu düsturda \(|N(u)\cap B_0|\), müdafiəçi \(u\)-nun 0 etiketli qonşularının sayıdır. Sağ tərəfdəki 1 termini müdafiəçinin öz qorunmasını, tavan funksiyası ilə hesablanan ikinci termin isə eyni anda müdafiə edə biləcəyi qorunmayan qonşular üçün lazım olan əlavə tutumu ifadə edir.

Güclü Roma dominantlıq ədədi

\[ \gamma_{StR}(G) \]

ilə göstərilir.

Mənbənin Şəkil 2-sində eyni nümunə qraf üçün klassik Roma dominantlıq çəkisi 6 olduğu halda güclü Roma dominantlıq çəkisi 8 kimi göstərilir. Bu vizual eyni vaxtda çoxsaylı hücum şərtinin eyni qraf üzərində daha çox ümumi müdafiə çəkisi tələb edə biləcəyini göstərmək üçün istifadə edilmişdir.

Ümumi aşağı və yuxarı sərhədlər

Mənbə daha əvvəl məlum olan üç əsas sərhəddən istifadə edir. Birincisi

\[ \gamma_R(G) \leq \gamma_{StR}(G) \leq \left( 1+\left\lceil\frac{\Delta}{2}\right\rceil \right)\gamma(G) \]

münasibəti verilir; burada \(\gamma(G)\) klassik dominantlıq ədədidir.

Mərtəbəsi \(n\) olan qraf üçün həmçinin

\[ \gamma_{StR}(G) \leq n-\left\lfloor\frac{\Delta}{2}\right\rfloor \]

yuxarı sərhədi və

\[ \gamma_{StR}(G) \geq \left\lceil\frac{n+1}{2}\right\rceil \]

aşağı sərhədi istifadə olunur. Bu sərhədlər sonrakı dəqiq-qiymət isbatlarında konstruktiv etiketləmənin verdiyi yuxarı sərhədlə məcburi aşağı sərhədin eyni qiymətdə birləşdirilməsinə kömək edir.

Qraf ailələri niyə vacibdir?

Ümumi optimallaşdırma probleminin bütün qraflarda həlli çətin ola bilər; lakin ağaclar, yollar, dövrlər, iki hissəli qraflar və ya məhdud clique-width sinifləri kimi struktur baxımından xüsusi qraf ailələrində daha güclü alqoritmik və qapalı-forma nəticələr əldə etmək mümkündür. Bu işin əsas yanaşması da ikitərəflidir: ümumi problemin hansı strukturlarda hesablama baxımından asan və ya çətin olduğunu müəyyən etmək və müəyyən qraf ailələrində optimal çəkini birbaşa düsturla hesablamaq.

İşdə istifadə olunan bəzi qraf ailələri

Tədqiqatın Metodu və Nəticələri

[k]-Roma dominantlığı hansı qraf siniflərində xətti zamanda həll edilə bilir?

[k]-Roma dominantlığı LinEMSOL optimallaşdırma problemi kimi ifadə oluna bildiyinə görə, məhdud clique-width-ə malik qraf sinfində uyğun \(r\)-ifadəsi girişlə birlikdə verilirsə və ya səmərəli şəkildə istehsal oluna bilirsə, minimum [k]-Roma dominantlıq funksiyası qrafın mərtəbəsinə görə xətti zamanda müəyyən edilə bilir.

MSOL və LinEMSOL yanaşması

Monadik İkinci Tərtib Məntiqi, yəni MSOL, yalnız fərdi təpələr üzərində deyil, təpə çoxluqları üzərində də kvantlaşdırmaya imkan verir. Qrafın bitişiklik əlaqəsi

\[ R(u,v) \]

ilə təmsil edildikdə çoxlu kombinatorik xüsusiyyətlər məntiqi düsturlarla müəyyən edilə bilər.

LinEMSOL bu strukturu monadik çoxluqların kardinal ölçülərindən qurulan xətti məqsəd funksiyaları ilə genişləndirir. Məqalədə [k]-Roma etiketləməsi

\[ f=(V_0,V_1,\ldots,V_{k+1}) \]

şəklində təpə çoxluqlarına ayrılır; \(V_j\), etiket qiyməti \(j\) olan təpələrin çoxluğudur.

Bu çoxluqların \(V\)-nin bir partition-ını təşkil etməsi və hər təpənin [k]-RDF şərtini ödəməsi məntiqi olaraq ifadə edilir. Optimallaşdırma məqsədi

\[ \min \left\{ \sum_{j=1}^{k+1}j|V_j| : \operatorname{Partition}(V) \land [k]\text{-}\operatorname{RDF} \right\} \]

şəklindədir.

Bu ifadə birbaşa etiket çəkisini minimuma endirir. Courcelle yanaşması sayəsində problem, uyğun parçalanma/təqdimat mövcud olduqda məhdud clique-width siniflərində xətti-zaman alqoritminə çevrilə bilər.

Mənbənin Corollary 2-sində nəticə \(f(k)\cdot n\) formasında verilir və nümunə siniflər kimi cographs, distance-hereditary graphs, complete graphs, trees, series-parallel graphs və outerplanar graphs sadalanır.

Güclü Roma dominantlığı niyə NP-tamdır?

İş güclü Roma dominantlığı qərar probleminin ulduz-konveks iki hissəli qraflarda NP-tamlığını Restricted Exact 3-Cover nümunəsindən müəyyən ulduz-konveks iki hissəli qraf yaradıb exact cover ilə aşağı çəkili güclü Roma etiketləməsinin mövcudluğunu bir-birinə ekvivalent etməklə sübut edir.

Qərar problemi

Giriş olaraq bir

\[ G=(V,E) \]

qrafı və müsbət \(k\) tam ədədi verilir. Sual belədir:

\[ \text{Ağırlığı }f(V)\leq k\text{ olan bir StRDF var mı?} \]

Namizəd etiketləmənin StRDF şərtlərini və çəki sərhədini polinom zamanda yoxlamaq mümkün olduğundan problem NP daxilindədir.

RX3C-dən reduksiya

Restricted Exact 3-Cover problemində

\[ |X|=3q \]

və \(C\), üçelementli altçoxluqlar ailəsidir; hər \(x\in X\) tam olaraq üç müxtəlif çoxluqda yer alır. Sual \(X\)-i kəsişməsiz şəkildə tam örtən bir \(C^\ast\subseteq C\) ailəsinin tapılıb-tapılmamasıdır.

Mənbə bu nümunədən \(\Gamma(I)\) adlı ulduz-konveks iki hissəli qraf yaradır və güclü Roma çəki həddini

\[ 6q+2 \]

kimi seçir.

Konstruksiyada iki hissəli siniflər

\[ A=\{a,x_i,z_i:i\in[3q]\}, \qquad B=\{c_j,a_1,a_2:j\in[3q]\} \]

şəklindədir. Buna görə

\[ |A|=6q+1, \qquad |B|=3q+2. \]

\(x_i\) təpəsi \(c_j\)-yə yalnız və yalnız müvafiq element müvafiq üçlü çoxluğun daxilindədirsə birləşdirilir. Bundan əlavə \(a\), bütün \(c_j\) təpələrinə və \(a_1,a_2\)-yə; hər \(c_j\) də öz \(z_j\)-sinə birləşdirilir.

PDF-nin Şəkil 3-ü bu reduksiya qrafının skeletini göstərir. Şəklin elmi funksiyası RX3C çoxluq üzvlüyünün qraf bitişiklik strukturuna necə kodlandığını görünən etməkdir.

İsbatın irəli istiqamətində exact cover \(C'\) varsa seçilmiş \(c_j\) təpələrinə 3, müəyyən \(z_i\) təpələrinə 1 və mərkəz \(a\)-ya \(q+2\) etiketi verilərək ümumi çəki

\[ (q+2)+3q+2q=6q+2 \]

olan güclü Roma dominantlıq funksiyası qurulur.

Tərs istiqamətdə çəkisi ən çox \(6q+2\) olan optimal StRDF-nin strukturu addım-addım məhdudlaşdırılaraq dəqiq olaraq \(q\) ədəd \(c_j\) təpəsinin 3 etiketini daşımalı olduğu və bunların \(X\)-in exact cover-ını yaratdığı göstərilir. Beləliklə RX3C nümunəsinin “bəli” cavabı ilə StRDN nümunəsinin “bəli” cavabı ekvivalent olur.

[k]-Roma dominantlığında dəstək təpələri

Mənbənin Lemma 1-i yarpaq və dəstək təpələrinin optimal etiketləmədə davranışını məhdudlaşdırır. \(k\geq2\) üçün zəif dəstək təpəsi \(v\) və ona bağlı yarpaq \(u\) üçün

\[ k\leq f(u)+f(v)\leq k+1. \]

Əgər cəm tam \(k\) olarsa, məcburi olaraq

\[ f(u)=k,\qquad f(v)=0. \]

Güclü dəstək təpəsi \(v\), yəni ən azı iki yarpağa qonşu olan təpə üçün isə optimal [k]-Roma etiketləməsində

\[ f(v)=k+1 \]

və \(v\)-yə bağlı bütün yarpaqlarda

\[ f(u)=0 \]

olduğu göstərilir. Bu lemma sonrakı ağac və ikiqat ulduz nəticələrinin əsas tikinti blokudur.

[k]-Roma dominantlığında hansı dəqiq qiymətlər əldə edildi?

İş ikiqat ulduzlar üçün birbaşa düsturlar, \(n\equiv0\pmod3\) olduqda yol və dövrlər üçün ortaq qapalı forma və yolların [k]-Roma reinforcement ədədi üçün konqruensiya siniflərindən asılı nəticələr əldə edir.

İkiqat ulduzlar

\(S_{1,q}\) bir zəif və bir güclü dəstək təpəsinə malik ikiqat ulduz olduqda

\[ \gamma_{[kR]}(S_{1,q})=2k+1 \]

nəticəsi əldə edilir.

Hər iki mərkəz ən azı iki yarpağa malikdirsə, yəni \(p,q\geq2\) üçün

\[ \gamma_{[kR]}(S_{p,q})=2k+2. \]

İkinci düsturun arxasındakı struktur sadədir: hər iki mərkəz güclü dəstək təpəsidir və Lemma 1-ə görə hər biri \(k+1\) çəki daşıyır; yarpaqların optimal etiketi 0-dır.

Yol və dövrlərdə etiket strukturu

Mənbə ən azı dörd təpəli yol və ya dövrdə minimum [k]-Roma funksiyasında müəyyən orta səviyyəli etiketlərin dörd ardıcıl təpədə davamlı təkrarlana bilməyəcəyini göstərir. \(k\) cüt olduqda qadağan edilmiş struktur üç ardıcıl təpəyə qədər güclənir.

Belə lokal struktur məhdudiyyətləri optimal etiketlərin hansı periodik naxışlar yarada biləcəyini anlamağa və dəqiq qiymətlərin çıxarılmasına kömək edir.

Yol ilə dövrün müqayisəsi

Dövr eyni mərtəbəli yolun üzərinə bir kənar əlavə etməklə alına bildiyindən mənbə

\[ \gamma_{[kR]}(C_n) \leq \gamma_{[kR]}(P_n) \]

bərabərsizliyini verir.

Müəyyən optimal yol etiketləməsində \(V_1=\varnothing\) və \(V_{k+1}=\varnothing\) şərtləri ödənirsə daha güclü nəticə

\[ \gamma_{[kR]}(C_n) \leq \gamma_{[kR]}(P_n)-1 \]

əldə edilir.

\(n\equiv0\pmod3\) halında dəqiq qiymət

\(n\) üçə bölünürsə həm \(P_n\), həm də \(C_n\) üçün səmərəli dominant çoxluq hər üç təpədən bir seçilə bilər. Bu halda

\[ \boxed{ \gamma_{[kR]}(C_n) = \gamma_{[kR]}(P_n) = (k+1)\frac{n}{3} } \]

olur.

Burada hər seçilmiş dominant təpə \(k+1\) çəkisi daşıyır və qapalı qonşuluqlar qrafı üst-üstə düşmədən örtür.

Yol qraflarında reinforcement

Mənbə [k]-Roma reinforcement ədədini \(r_{[kR]}(G)\) ilə göstərir və əsas məqsəd kimi qrafın [k]-Roma dominantlıq ədədini azaltmaq üçün neçə yeni kənarın yetərli olduğunu araşdırır.

Mənbədaxili notasiya xəbərdarlığı: Definition 1-də \(F\subseteq E(G)\) yazılıb; lakin eyni tərif \(G+F\)-i “\(F\)-dəki kənarların əlavə edilməsi” kimi izah edir və sonrakı isbatda başlanğıc yolunda olmayan kənarlar əlavə edilir. Buna görə burada tərifin çap olunmuş ifadəsi səssizcə dəyişdirilməyib, nəticələr Proposition 10-dakı açıq konstruksiyalar əsasında verilib.

\(n\geq4\) üçün mənbə

\[ r_{[kR]}(P_n)\in\{1,2\} \]

nəticəsini verir.

İsbatda istifadə olunan yol qiymətləri müvafiq olaraq

\[ \gamma_{[kR]}(P_n) = (k+1)\frac{n}{3}, \qquad n\equiv0\pmod3, \]

\[ \gamma_{[kR]}(P_n) = (k+1)\left\lfloor\frac{n}{3}\right\rfloor+k, \qquad n\equiv1\pmod3, \]

və

\[ \gamma_{[kR]}(P_n) = (k+1)\left\lfloor\frac{n}{3}\right\rfloor+k+1, \qquad n\equiv2\pmod3 \]

şəklindədir.

Güclü Roma dominantlığında hansı qraf ailələri üçün dəqiq düsturlar tapıldı?

İş \(t\)-qatlı çarxlar, tac qrafları, \(C_m\circ K_1\) korona qrafları və hər onurğa təpəsində ən azı iki yarpaq olan müəyyən tırtıl qrafları üçün güclü Roma dominantlıq ədədini tam müəyyən edir; daha ümumi tırtıllar üçün isə yuxarı sərhəd verir.

\(t\)-qatlı çarxlar

\(W_{m,t}\), bir \(C_m\) dövrünə bir-biri ilə qonşu olmayan \(t\) mərkəz təpənin birləşdirilməsi ilə yaradılır. Proposition 11 güclü Roma dominantlıq ədədinin \(m\) və \(t\)-nin böyüklük və paritet şərtlərindən asılı olaraq dəyişdiyini göstərir:

\[ \gamma_{StR}(W_{m,t})= \begin{cases} \left\lceil\dfrac{t}{2}\right\rceil+2, & m=3,\ t\geq2,\\[6pt] \left\lceil\dfrac{t}{2}\right\rceil+3, & m=4,\ t\geq2,\\[6pt] \left\lceil\dfrac{m}{2}\right\rceil+t, & m\geq5,\ t=2,\\ & \text{veya }m\text{ çift},\ m\geq5,\ t=3,\\[6pt] \left\lceil\dfrac{m-1}{2}\right\rceil+ \left\lceil\dfrac{t+1}{2}\right\rceil+2, & m,t\text{ tek},\ m\geq5,\ t\geq3,\\ & \text{veya }m\geq6,\ t\geq4,\ m+t\text{ tek},\\[6pt] \dfrac{t}{2}+4, & m=5,\ t\text{ çift},\ t\geq4,\\[6pt] \dfrac{m}{2}+\dfrac{t}{2}+2, & m,t\text{ çift},\ m\geq6,\ t\geq4. \end{cases} \]

Bu hissəli struktur təsadüfi deyil. Dövr təpələrinin və mərkəz təpələrin neçə qorunmayan qonşunu eyni anda müdafiə etməli olduğu \(m\) və \(t\)-nin paritetindən asılı olaraq optimal güclü təpə yerləşimini dəyişir.

Tac qrafı

Tac qrafı \(C(n)\), \(K_{n,n}\)-dən tam uyğunlaşdırma çıxarılaraq əldə edilir və cəmi \(2n\) təpə ehtiva edir. Mənbə aşağıdakı dəqiq qiyməti verir:

\[ \boxed{ \gamma_{StR}(C(n))= \begin{cases} n+1,&n\equiv1\pmod2,\\ n+2,&n\equiv0\pmod2. \end{cases} } \]

Tək \(n\)-də ümumi aşağı sərhədlə konstruktiv yuxarı sərhəd üst-üstə düşərək \(n+1\)-i verir. Cüt \(n\)-də optimal həlldə iki müxtəlif iki hissəli sinifdə güclü təpə olmalı olduğu göstərilərək aşağı sərhəd \(n+2\)-yə qaldırılır.

PDF-nin Şəkil 4-ü \(C(3)\) tac qrafında minimum güclü Roma dominantlıq funksiyasının nümunəsini göstərir.

Dövr-korona qrafı \(C_m\circ K_1\)

Dövrün hər təpəsinə bir yarpaq əlavə edildikdə \(C_m\circ K_1\) qrafı yaranır. Proposition 13 aşağıdakı dəqiq düsturu verir:

\[ \boxed{ \gamma_{StR}(C_m\circ K_1)= \begin{cases} \dfrac{3m}{2},&m\equiv0\pmod4,\\[6pt] \dfrac{3m+1}{2},&m\equiv1\pmod2,\\[6pt] \dfrac{3m+2}{2},&m\equiv2\pmod4. \end{cases} } \]

Yuxarı sərhəd dövr təpələri üzərində hər dörd təpədən bir təkrarlanan xüsusi \(2,0,0,2\)-yə bənzər etiket strukturu və yarpaq etiketlərindən istifadə etməklə qurulur. Aşağı sərhəddə isə xüsusilə \(m\equiv0\pmod4\) halında discharging, yəni yükün yenidən paylanması arqumentindən istifadə edilir.

Discharging üsulu nə edir?

İsbatda başlanğıcda hər təpənin yükü öz etiketi kimi götürülür:

\[ s_0(v)=f(v). \]

Daha sonra bəzi yarpaqlardan dövr təpələrinə və 2 etiketli dövr təpələrindən qonşularına yarım və ya bir tam vahidlik yüklər ötürülür. Bu ötürmə ümumi yükü dəyişmir:

\[ \sum_{v\in V}s(v) = \sum_{v\in V}f(v). \]

Lakin yenidən paylanmış yüklər dövr təpələrinin hər biri üzərində ən azı \(3/2\)-lik orta töhfə əldə etməyi mümkün edir. Nəticədə

\[ \gamma_{StR}(G) \geq \frac{3m}{2} \]

aşağı sərhədi ortaya çıxır və konstruktiv yuxarı sərhədlə üst-üstə düşdükdə dəqiq qiymət sübut olunmuş olur.

Xüsusi tırtıl qrafları

Onurğa \(v_1,\ldots,v_n\) təpələrindən ibarət olsun və hər \(v_i\)-yə

\[ x_i\geq2 \]

yarpaq bağlı olsun. Bu halda hər onurğa təpəsi güclü dəstək təpəsidir. Proposition 14:

\[ \boxed{ \gamma_{StR}(C) = \sum_{i=1}^{n} \left( 1+ \left\lceil\frac{x_i}{2}\right\rceil \right) } \]

dəqiq qiymətini verir.

Yuxarı sərhəd üçün hər onurğa təpəsinə

\[ f(v_i)= 1+ \left\lceil\frac{x_i}{2}\right\rceil \]

etiketi, bütün yarpaqlara isə 0 etiketi verilir. Aşağı sərhəd isə hər güclü dəstək təpəsinin və yarpaqlarının ümumilikdə ən azı eyni çəkini tələb etməsi əsasında əldə edilir.

PDF-nin Şəkil 5-i bu strukturu vizual olaraq göstərir: onurğa üzərindəki güclü dəstək təpələri 2 və ya 3 kimi müsbət etiketlər daşıyarkən bağlı yarpaqlar 0 etiketlidir. Şəklin rolu qapalı düsturdakı hər onurğa təpəsinin lokal töhfəsini vizuallaşdırmaqdır.

Daha ümumi tırtıl qrafı üçün yuxarı sərhəd

Mənbə sonda onurğada güclü dəstək təpələrinə əlavə olaraq \(k\) ədəd zəif dəstək təpəsinə və dəstək təpələri arasında dəstək olmayan təpələrdən ibarət \(q\) ədəd \(P_{r_j}\) alt yoluna icazə verir. Bu daha ümumi halda dəqiq qiymət deyil, aşağıdakı yuxarı sərhəd verilir:

\[ \boxed{ \gamma_{StR}(C) \leq \sum_{i=1}^{n} \left( 1+\left\lceil\frac{x_i}{2}\right\rceil \right) + 2k + \sum_{j=1}^{q} \left\lceil\frac{2r_j}{3}\right\rceil } \]

İlk cəm güclü dəstək təpələrini və onların yarpaqlarını, \(2k\) termini zəif dəstək təpələrini, son cəm isə dəstək təpələri arasındakı ara yolların güclü Roma dominantlıq xərcini ifadə edir.

Mənbə şəkillərinin elmi funksiyaları

İşin dəstəklədiyi nəticələr

İş [k]-Roma dominantlığının uyğun struktur qraf siniflərində LinEMSOL və Courcelle çərçivəsi ilə xətti-zaman həllinə endirilə bildiyini; güclü Roma dominantlığının ulduz-konveks iki hissəli qraflarda NP-tam olduğunu; həmçinin müəyyən ikiqat ulduz, yol, dövr, çarx, tac, korona və tırtıl ailələrində dominantlıq parametrlərinin qapalı formada hesablana bildiyini riyazi isbatlarla dəstəkləyir.

Nəticələr həmçinin qraf optimallaşdırma probleminin mürəkkəbliyinin yalnız təpə və kənar sayından deyil, qrafın struktur sinfindən də güclü şəkildə asılı olduğunu göstərir: ümumi və ya müəyyən iki hissəli siniflərdə qərar problemi çətin ola bilərkən məhdud clique-width/treewidth strukturu əlavə alqoritmik üstünlük verir.

İşin dəstəkləmədiyi nəticələr

Məqalə real hərbi, logistika və ya infrastruktur şəbəkəsində təcrübə aparmır. “Müdafiə vahidi” dili qraf nəzəriyyəsinin tarixi və konseptual şərhidir. Nəticələr real dünyadakı resurs bölgüsünə birbaşa performans zəmanəti vermir. LinEMSOL nəticəsi bütün qraflarda xətti-zaman alqoritmi olduğu demək deyil; məhdud clique-width və uyğun təqdimat fərziyyəsindən asılıdır. NP-tamlıq nəticəsi də hər bir ayrıca qraf nümunəsinin praktikada həll edilə bilməyəcəyi demək deyil; problem sinfinin ən pis hal hesablama mürəkkəbliyini ifadə edir.

Eyni şəkildə, t-qatlı çarx, tac, korona və xüsusi tırtıl qraf düsturları yalnız göstərilən qraf ailələri və parametr şərtləri üçün keçərlidir; ixtiyari qrafın güclü Roma dominantlıq ədədini bu düsturlardan çıxarmaq mümkün deyil.

Mənbədəki iki notasiya problemi

Birincisi, giriş hissəsində \(P_n\), uzunluğu \(n\) olan və \(u_0,u_1,\ldots,u_n\) təpələrindən ibarət yol kimi müəyyən edildiyi halda sonrakı nəticələrdə \(P_n\), “mərtəbəsi \(n\)” olan yol mənasında istifadə edilir. Buna görə bu Verianla mətnində nəticələr verildikdə müvafiq teorem və ya təklifin öz “mərtəbə \(n\)” ifadəsi əsas götürülüb; giriş tərifi səssizcə yenidən yazılmayıb.

İkincisi, [k]-Roma reinforcement tərifində mənbə \(F\subseteq E(G)\) yazır; buna baxmayaraq \(G+F\)-i kənar əlavəetmə əməliyyatı kimi müəyyən edir və Proposition 10-un konstruksiyalarında yolun mövcud kənarı olmayan \(v_2v_4\), \(v_6v_8\), \(v_1v_3\) və \(v_1v_4\) kənarlarını əlavə edir. Bu açıq mənbədaxili uyğunsuzluq səbəbindən Verianla tərifdəki çoxluq ifadəsini fərziyyəyə əsasən dəyişməyib.

Mənbə və Metod Qeydi

Orijinal iş: Complexity and Exact Values for [k]-Roman and Strong Roman Domination for Specific Graph Families

Müəlliflər: Juan Carlos Valenzuela-Tripodoro; María Antonia Mateos-Camacho; Martín Cera López; María Pilar Álvarez-Ruíz.

Corresponding author: Juan Carlos Valenzuela-Tripodoro.

Qurumlar: Departamento de Matemáticas, Universidad de Cádiz, Algeciras, İspanya; Departamento de Matemática Aplicada I, Universidad de Sevilla, Sevilla, İspanya; Departamento de Estadística e IO, Universidad de Cádiz, Algeciras, İspanya.

Jurnal: Mathematics.

Nəşriyyat: MDPI.

Biblioqrafik qeyd: Mathematics 2026, 14(9), 1535.

DOI: 10.3390/math14091535.

Məqalə prosesi: Alınma 19 Fevral 2026; reviziya 6 Aprel 2026; qəbul 28 Aprel 2026; nəşr 1 May 2026.

Mənbə növü: Resenziyalı nəzəri riyaziyyat / diskret riyaziyyat / qraf nəzəriyyəsi tədqiqat məqaləsi.

Lisenziya: Creative Commons Attribution (CC BY).

Verilənlərin vəziyyəti: Müəlliflər işdə yeni verilənlərin yaradılmadığını və ya təhlil edilmədiyini bildirirlər. İşin sübut materialını qraf strukturları, riyazi təriflər, teoremlər, təkliflər və isbatlar təşkil edir.

Müəllif töhfələri: Konseptuallaşdırma, metodologiya, doğrulama və tədqiqata dörd müəllifin hamısı töhfə verib. İlk qaralama Martín Cera López və María Pilar Álvarez-Ruíz; nəzərdən keçirmə və redaktə Juan Carlos Valenzuela-Tripodoro və María Antonia Mateos-Camacho tərəfindən həyata keçirilib. Mənbə bütün müəlliflərin işə bərabər töhfə verdiyini ayrıca bildirir.

Maliyyələşdirmə: Juan Carlos Valenzuela-Tripodoro; İspaniya Elm, İnnovasiya və Universitetlər Nazirliyinin PID2022-139543OB-C41 layihəsi və Avropa Komissiyasının Horizon Europe Marie Skłodowska-Curie Actions Staff Exchanges çərçivəsindəki 101182819 nömrəli COVER layihəsi tərəfindən qismən dəstəklənib. Martín Cera López; Andalusiya Regional Hökumətinin Tədqiqat, İnkişaf və İnnovasiya Planı çərçivəsindəki FQM-240 layihəsi və PPIT-FEDER SOL2024-31708 “Mathematics for Cybersecurity and Smart City Development” layihəsindən qismən dəstək alıb.

Maraqların toqquşması: Müəlliflər maraqların toqquşmasını bildirməyiblər.

Mənbə strukturu qeydi: Məqalədə ayrıca “Conclusions” bölməsi yoxdur. Əsas elmi məzmun Proposition 15 ilə bitdikdən sonra müəllif töhfələri, maliyyələşdirmə, verilənlərin əlçatanlığı və maraqların toqquşması bəyanatları gəlir. Buna görə Verianla-dakı “işin dəstəklədiyi / dəstəkləmədiyi” qiymətləndirmələri yalnız məqalədə sübut edilmiş nəticələrdən çıxarılıb; mənbəyə aid olmayan yeni nəticə bölməsi kimi təqdim edilməyib.

Əsas metodoloji sərhəd: İş eksperimental və ya empirik deyil. Alqoritmik mürəkkəblik nəticələri göstərilən qraf sinfi və təqdimat fərziyyələrindən; dəqiq-qiymət düsturları isə müvafiq qraf ailələri, paritet və konqruensiya şərtlərindən asılıdır.

Notasiya sərhədi: Mənbədəki \(P_n\) uzunluq/mərtəbə istifadəsi ilə reinforcement tərifindəki \(F\subseteq E(G)\) ifadəsi mənbədə göründüyü kimi daxili uyğunsuzluq daşıyır. Bu Verianla mətni həmin nöqtələri gizlətməyib və məlum olmayan düzəlişi mənbə nəticəsi kimi təqdim etməyib.

Vizualın yenidən çəkilmə uyğunluğu: Uyğundur. Beş mənbə şəklinin hamısı qraf-nəzəri sxem olduğundan düyün mövqeləri və etiketləmə məntiqi qorunmaqla Verianla üçün orijinal vektor qraf sxemləri yaradıla bilər. Məqsəd piksel kopyalama deyil, eyni riyazi əlaqəni yeni dizaynla görünən etməkdir.

Verianla Live / Live Figure: Qismən uyğundur. Xüsusilə Şəkil 1–2-də etiketlərin müdafiə şərtini necə ödədiyinin ardıcıl vurğulanması və Şəkil 3-də RX3C-dən \(\Gamma(I)\)-yə çevrilmənin mərhələli göstərilməsi source-derived Live Figure kimi dəyərlidir. İstifadəçinin qrafı və ya \(k\) qiymətini dəyişdirib yeni optimal nəticə yaratmasına icazə verilməməlidir; bu, mənbədə edilməyən yeni hesablama olar.