Roma dominantligi graf cho‘qqilariga mudofaa resursi sifatida talqin qilinadigan butun sonli yorliqlar berib, barcha cho‘qqilarni muayyan qo‘shnichilik shartlari ostida himoyalash bilan birga yorliqlarning umumiy og‘irligini minimallashtirishni ko‘zlaydigan graf optimallashtirish modelidir. Juan Carlos Valenzuela-Tripodoro, María Antonia Mateos-Camacho, Martín Cera López va María Pilar Álvarez-Ruízning tadqiqoti ushbu modelning ikki rivojlangan ko‘rinishini — [k]-Roma dominantligi va kuchli Roma dominantligini — ham hisoblash murakkabligi, ham muayyan graf oilalaridagi aniq parametr qiymatlari nuqtai nazaridan o‘rganadi.

[k]-Roma dominantligi tomonida mualliflar masalani Linear Extended Monadic Second-Order Logic (LinEMSOL) shaklida ifodalaydi. Natijada mos graf tasviri mavjud bo‘lsa, cheklangan clique-width sinflarida masala graf tartibiga nisbatan chiziqli vaqtda yechilishi mumkin. Kuchli Roma dominantligi tomonida esa qaror masalasining yulduz-konveks ikki bo‘lakli graflarda NP-to‘liq ekani Restricted Exact 3-Cover masalasidan qurilgan reduksiya orqali ko‘rsatiladi.

Tadqiqotning ikkinchi asosiy yo‘nalishi aniq qiymatlardir. Ikki yulduzli daraxtlar, ayrim yo‘llar va sikllar, t-qavatli g‘ildiraklar, toj graflari, sikl bilan bitta cho‘qqining korona ko‘paytmasi hamda ayrim tırtıl graf sinflari uchun [k]-Roma yoki kuchli Roma dominantlik sonlari aniqlanadi. Natijalar eksperimental emas; ular graf yorliqlashlari, kombinatorik quyi va yuqori chegaralar, mantiqiy ifodalanuvchanlik, murakkablik reduksiyalari va konstruktiv isbotlarga tayangan.

Roma dominantligi nima?

Roma dominantligi graf cho‘qqilariga 0, 1 yoki 2 yorliqlarini beradigan va 0 yorliqli har bir cho‘qqining kamida bitta 2 yorliqli qo‘shniga ega bo‘lishini talab qiladigan cho‘qqi-yorliqlash optimallashtirish modelidir; maqsad barcha yorliqlarning umumiy og‘irligini minimallashtirishdir.

Sodda, yo‘naltirilmagan va chekli graf

\[ G=(V,E) \]

bilan belgilansin. Bu yerda \(V\) cho‘qqilar to‘plamini, \(E\) esa qirralar to‘plamini bildiradi. Klassik Roma dominantlik funksiyasi

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

ko‘rinishidadir. Agar \(f(v)=0\) bo‘lsa, \(v\) ning kamida bitta qo‘shnisi \(u\) uchun

\[ f(u)=2 \]

bo‘lishi kerak.

Funksiyaning og‘irligi

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

ko‘rinishidadir. Grafning Roma dominantlik soni

\[ \gamma_R(G) \]

esa barcha yaroqli Roma dominantlik funksiyalari orasidagi eng kichik og‘irlikdir.

“Roma” nomi tarixiy mudofaa o‘xshatishidan kelib chiqadi: 0 yorliqli joyda bevosita mudofaa birligi yo‘q; ammo qo‘shni joyda ikki birlik bo‘lsa, ushbu qo‘shni o‘z mudofaasini butunlay yo‘qotmasdan bir birlikni yordamga yuborishi mumkin. Matematik jihatdan muhim narsa tarixiy hikoya emas, balki grafdagi mahalliy himoya shartlari bilan umumiy resurs xarajatini birgalikda optimallashtirishdir.

Qo‘shnichilik va faol qo‘shnichilik

Bir \(u\) cho‘qqining ochiq qo‘shnichiligi \(N(u)\), \(u\) ga tutash cho‘qqilar to‘plamidir. Yopiq qo‘shnichilik esa

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

deb ta’riflanadi.

Bir yorliqlash \(f\) berilganda faol qo‘shnichilik

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

to‘plamidir. Bu tushuncha ayniqsa [k]-Roma dominantligi ta’rifida markaziy o‘rin tutadi.

[k]-Roma dominantligi klassik modeldan qanday farq qiladi?

\[k]-Roma dominantligi har bir cho‘qqiga \(0\) bilan \(k+1\) orasidagi yorliqni berishga ruxsat beradi va har bir cho‘qqining yopiq qo‘shnichiligidagi umumiy yorliq qiymatini kamida \(k\) ga faol qo‘shnilar soni qo‘shilgan miqdorga tenglashtirish orqali klassik Roma dominantligini yanada umumiy resurs-taqsimlash modeliga aylantiradi.

Bir [k]-Roma dominantlik funksiyasi, qisqacha [k]-RDF,

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

ko‘rinishida ta’riflanadi va har bir \(u\in V\) uchun

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

shartini qanoatlantirishi kerak.

Bu yerda

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

yopiq qo‘shnichilikdagi yorliqlar yig‘indisidir. \(|AN(u)|\), \(u\) ning musbat yorliq tashuvchi faol qo‘shnilari sonidir. Demak, talab qilinadigan minimal yig‘indi faqat \(k\) ga emas, balki shu cho‘qqi atrofida nechta faol cho‘qqi mavjudligiga ham bog‘liq.

Grafdagi minimal [k]-Roma dominantlik og‘irligi

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

bilan belgilanadi.

Manbaning 1-rasmida bir xil grafda klassik Roma dominantlik yorliqlashi bilan [k]-Roma yorliqlashi yonma-yon ko‘rsatilgan. Misolda klassik qiymat

\[ \gamma_R(G)=6 \]

bo‘lsa, ko‘rsatilgan [k]-Roma qiymati

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

ko‘rinishidadir. Bular barcha graflar uchun umumiy formulalar emas, balki 1-rasmdagi muayyan graf yorliqlashlarini izohlovchi qiymatlardir.

Kuchli Roma dominantligi nimani modellashtiradi?

Kuchli Roma dominantligi bitta hujum o‘rniga bir vaqtning o‘zida bir nechta himoyasiz qo‘shnini himoya qilishni modellashtirish uchun musbat yorliq tashuvchi kuchli cho‘qqining 0 yorliqli qo‘shnilarining kamida yarmiga yetadigan mudofaa og‘irligini olib yurishini talab qiladigan Roma dominantligi variantidir.

Grafning maksimal darajasi \(\Delta\) bo‘lsin. Kuchli Roma dominantlik funksiyasi, qisqacha StRDF, cho‘qqilarni

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

to‘plamidan yorliqlaydi.

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

0 yorliqli cho‘qqilar to‘plami bo‘lsin; har bir \(v\in B_0\) uchun bir qo‘shni \(u\) topilishi va

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

sharti bajarilishi kerak.

Bu formulada \(|N(u)\cap B_0|\), himoyachi \(u\) ning 0 yorliqli qo‘shnilari sonidir. O‘ng tomondagi 1 hadi himoyachining o‘z himoyasini, shift funksiyasi bilan hisoblangan ikkinchi had esa bir vaqtning o‘zida himoya qilishi mumkin bo‘lgan himoyasiz qo‘shnilar uchun zarur qo‘shimcha quvvatni ifodalaydi.

Kuchli Roma dominantlik soni

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

bilan belgilanadi.

Manbaning 2-rasmida bir xil misol graf uchun klassik Roma dominantlik og‘irligi 6, kuchli Roma dominantlik og‘irligi esa 8 sifatida ko‘rsatilgan. Ushbu tasvir bir vaqtning o‘zida ko‘p hujum sharti bir xil grafda ko‘proq umumiy mudofaa og‘irligini talab qilishi mumkinligini ko‘rsatish uchun ishlatilgan.

Umumiy quyi va yuqori chegaralar

Manba avvaldan ma’lum bo‘lgan uchta asosiy chegaradan foydalanadi. Avvalo

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

munosabati beriladi; bu yerda \(\gamma(G)\) klassik dominantlik sonidir.

Tartibi \(n\) bo‘lgan graf uchun qo‘shimcha ravishda

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

yuqori chegarasi va

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

quyi chegarasi qo‘llanadi. Bu chegaralar keyingi aniq-qiymat isbotlarida konstruktiv yorliqlash bergan yuqori chegara bilan majburiy quyi chegarani bir qiymatda uchrashtirishga yordam beradi.

Graf oilalari nima uchun muhim?

Umumiy optimallashtirish masalasini barcha graflarda yechish qiyin bo‘lishi mumkin; biroq daraxtlar, yo‘llar, sikllar, ikki bo‘lakli graflar yoki cheklangan clique-width sinflari kabi struktur jihatdan maxsus graf oilalarida kuchliroq algoritmik va yopiq-formali natijalar olish mumkin. Ushbu tadqiqotning asosiy yondashuvi ham ikki yo‘nalishli: umumiy masala qaysi strukturalarda hisoblash nuqtai nazaridan oson yoki qiyin ekanini aniqlash va muayyan graf oilalarida optimal og‘irlikni bevosita formula bilan hisoblash.

Tadqiqotda ishlatilgan ayrim graf oilalari

Tadqiqot Usuli va Natijalari

[k]-Roma dominantligi qaysi graf sinflarida chiziqli vaqtda yechilishi mumkin?

[k]-Roma dominantligi LinEMSOL optimallashtirish masalasi sifatida ifodalanishi mumkinligi sababli, cheklangan clique-width ga ega graf sinfida mos \(r\)-ifoda kirish bilan birga berilsa yoki samarali hosil qilinsa, minimal [k]-Roma dominantlik funksiyasi graf tartibiga nisbatan chiziqli vaqtda aniqlanishi mumkin.

MSOL va LinEMSOL yondashuvi

Monadik Ikkinchi Tartibli Mantiq, ya’ni MSOL, faqat alohida cho‘qqilar ustida emas, balki cho‘qqilar to‘plamlari ustida ham kvantifikatsiya qilishga imkon beradi. Grafning tutashlik munosabati

\[ R(u,v) \]

bilan ifodalanganda ko‘plab kombinatorik xususiyatlarni mantiqiy formulalar bilan ta’riflash mumkin.

LinEMSOL ushbu tuzilmani monadik to‘plamlarning kardinalliklaridan tuzilgan chiziqli maqsad funksiyalari bilan kengaytiradi. Maqolada [k]-Roma yorliqlashi

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

ko‘rinishida cho‘qqilar to‘plamlariga ajratiladi; \(V_j\), yorliq qiymati \(j\) bo‘lgan cho‘qqilar to‘plamidir.

Bu to‘plamlarning \(V\) ning partition ini hosil qilishi va har bir cho‘qqi [k]-RDF shartini qanoatlantirishi mantiqiy tarzda ifodalanadi. Optimallashtirish maqsadi

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

ko‘rinishidadir.

Bu ifoda bevosita yorliq og‘irligini minimallashtiradi. Courcelle yondashuvi tufayli masala, mos dekompozitsiya/tasvir mavjud bo‘lganda, cheklangan clique-width sinflarida chiziqli-vaqt algoritmiga o‘tkazilishi mumkin.

Manbaning Corollary 2 qismida natija \(f(k)\cdot n\) ko‘rinishida beriladi va namunaviy sinflar sifatida cographs, distance-hereditary graphs, complete graphs, trees, series-parallel graphs va outerplanar graphs sanab o‘tiladi.

Kuchli Roma dominantligi nima uchun NP-to‘liq?

Tadqiqot kuchli Roma dominantligi qaror masalasining yulduz-konveks ikki bo‘lakli graflarda NP-to‘liqligini Restricted Exact 3-Cover misolidan muayyan yulduz-konveks ikki bo‘lakli graf hosil qilib, exact cover mavjudligi bilan kichik og‘irlikli kuchli Roma yorliqlashi mavjudligini o‘zaro ekvivalent qilish orqali isbotlaydi.

Qaror masalasi

Kirish sifatida bir

\[ G=(V,E) \]

graf va musbat \(k\) butun soni beriladi. Savol quyidagicha:

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

Nomzod yorliqlashning StRDF shartlari va og‘irlik chegarasini polinomial vaqtda tekshirish mumkin bo‘lgani uchun masala NP ichidadir.

RX3C dan reduksiya

Restricted Exact 3-Cover masalasida

\[ |X|=3q \]

va \(C\), uch elementli qism to‘plamlar oilasidir; har bir \(x\in X\) aynan uch xil to‘plamda qatnashadi. Savol \(X\) ni kesishmasdan to‘liq qoplaydigan bir \(C^\ast\subseteq C\) oilasi topiladimi yoki yo‘qmi.

Manba ushbu misoldan \(\Gamma(I)\) nomli yulduz-konveks ikki bo‘lakli graf yaratadi va kuchli Roma og‘irlik chegarasini

\[ 6q+2 \]

deb tanlaydi.

Qurilishda ikki bo‘lakli sinflar

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

ko‘rinishidadir. Shuning uchun

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

\(x_i\) cho‘qqi \(c_j\) ga faqat va faqat tegishli element tegishli uchlik to‘plam ichida bo‘lsa ulanadi. Bundan tashqari \(a\), barcha \(c_j\) cho‘qqilariga va \(a_1,a_2\) ga; har bir \(c_j\) esa o‘zining \(z_j\) siga ulanadi.

PDFning 3-rasmi ushbu reduksiya grafining skeletini ko‘rsatadi. Rasmning ilmiy vazifasi RX3C to‘plam a’zoligining graf tutashlik tuzilmasiga qanday kodlanishini ko‘rsatishdir.

Isbotning to‘g‘ri yo‘nalishida exact cover \(C'\) mavjud bo‘lsa, tanlangan \(c_j\) cho‘qqilariga 3, ayrim \(z_i\) cho‘qqilariga 1 va markaz \(a\) ga \(q+2\) yorliq berilib, umumiy og‘irligi

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

bo‘lgan kuchli Roma dominantlik funksiyasi quriladi.

Teskari yo‘nalishda og‘irligi eng ko‘pi bilan \(6q+2\) bo‘lgan optimal StRDF ning tuzilishi bosqichma-bosqich cheklanib, aynan \(q\) ta \(c_j\) cho‘qqisi 3 yorlig‘ini olishi kerakligi va ular \(X\) ning exact cover ini hosil qilishi ko‘rsatiladi. Shunday qilib RX3C misolining “ha” javobi bilan StRDN misolining “ha” javobi ekvivalent bo‘ladi.

[k]-Roma dominantligida tayanch cho‘qqilar

Manbaning Lemma 1 qismi barg va tayanch cho‘qqilarning optimal yorliqlashdagi xatti-harakatini cheklaydi. \(k\geq2\) uchun kuchsiz tayanch cho‘qqi \(v\) va unga ulangan barg \(u\) uchun

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

Agar yig‘indi aynan \(k\) bo‘lsa, majburiy ravishda

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

Kuchli tayanch cho‘qqi \(v\), ya’ni kamida ikki bargga qo‘shni cho‘qqi uchun optimal [k]-Roma yorliqlashda

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

va \(v\) ga ulangan barcha barglarda

\[ f(u)=0 \]

bo‘lishi ko‘rsatiladi. Ushbu lemma keyingi daraxt va ikki yulduz natijalarining asosiy qurilish blokidir.

[k]-Roma dominantligida qanday aniq qiymatlar olindi?

Tadqiqot ikki yulduzlar uchun bevosita formulalar, \(n\equiv0\pmod3\) bo‘lganda yo‘l va sikllar uchun umumiy yopiq formula hamda yo‘llarning [k]-Roma reinforcement soni uchun kongruensiya sinflariga bog‘liq natijalarni beradi.

Ikki yulduzlar

\(S_{1,q}\) bitta kuchsiz va bitta kuchli tayanch cho‘qqiga ega ikki yulduz bo‘lganda

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

natijasi olinadi.

Har ikki markaz kamida ikki bargga ega bo‘lsa, ya’ni \(p,q\geq2\) uchun

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

Ikkinchi formula ortidagi tuzilish sodda: ikki markaz ham kuchli tayanch cho‘qqidir va Lemma 1 ga ko‘ra har biri \(k+1\) og‘irlik tashiydi; barglarning optimal yorlig‘i 0 ga teng.

Yo‘l va sikllarda yorliq tuzilishi

Manba kamida to‘rtta cho‘qqili yo‘l yoki siklda minimal [k]-Roma funksiyasida muayyan o‘rta darajadagi yorliqlar to‘rtta ketma-ket cho‘qqida uzluksiz takrorlana olmasligini ko‘rsatadi. \(k\) juft bo‘lganda taqiqlangan tuzilish uchta ketma-ket cho‘qqigacha kuchayadi.

Bunday mahalliy struktur cheklovlar optimal yorliqlar qanday davriy naqshlar hosil qilishi mumkinligini tushunishga va aniq qiymatlarni keltirib chiqarishga yordam beradi.

Yo‘l va sikl taqqoslanishi

Sikl bir xil tartibli yo‘lga bitta qirra qo‘shish orqali olinishi mumkinligi sababli, manba

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

tengsizlikni beradi.

Muayyan optimal yo‘l yorliqlashida \(V_1=\varnothing\) va \(V_{k+1}=\varnothing\) shartlari bajarilsa, kuchliroq natija

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

olinadi.

\(n\equiv0\pmod3\) holatidagi aniq qiymat

\(n\) uchga bo‘linsa, ham \(P_n\), ham \(C_n\) uchun samarali dominant to‘plam har uch cho‘qqidan birini tanlash orqali tuzilishi mumkin. Bu holda

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

bo‘ladi.

Bu yerda har bir tanlangan dominant cho‘qqi \(k+1\) og‘irlikni tashiydi va yopiq qo‘shnichiliklar grafni ustma-ust tushmasdan qoplaydi.

Yo‘l graflarida reinforcement

Manba [k]-Roma reinforcement sonini \(r_{[kR]}(G)\) bilan belgilaydi va asosiy maqsad sifatida grafning [k]-Roma dominantlik sonini kamaytirish uchun nechta yangi qirra yetarli ekanini o‘rganadi.

Manba ichidagi notatsiya ogohlantirishi: Definition 1 da \(F\subseteq E(G)\) yozilgan; biroq ayni ta’rif \(G+F\) ni “\(F\) dagi qirralarni qo‘shish” sifatida izohlaydi va keyingi isbotda boshlang‘ich yo‘lda bo‘lmagan qirralar qo‘shiladi. Shu sababli bu yerda ta’rifning bosma ifodasi sukut bilan o‘zgartirilmagan, natijalar Proposition 10 dagi aniq konstruksiyalar asosida berilgan.

\(n\geq4\) uchun manba

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

natijasini beradi.

Isbotda ishlatilgan yo‘l qiymatlari mos ravishda

\[ \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, \]

va

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

ko‘rinishidadir.

Kuchli Roma dominantligida qaysi graf oilalari uchun aniq formulalar topildi?

Tadqiqot \(t\)-qavatli g‘ildiraklar, toj graflari, \(C_m\circ K_1\) korona graflari va har bir umurtqa cho‘qqisida kamida ikki barg bo‘lgan ayrim tırtıl graflari uchun kuchli Roma dominantlik sonini aniq belgilaydi; umumiyroq tırtıl graflari uchun esa yuqori chegara beradi.

\(t\)-qavatli g‘ildiraklar

\(W_{m,t}\), bir \(C_m\) sikliga o‘zaro qo‘shni bo‘lmagan \(t\) markaz cho‘qqi ulanishi orqali hosil qilinadi. Proposition 11 kuchli Roma dominantlik soni \(m\) va \(t\) ning kattalik va paritet shartlariga qarab o‘zgarishini ko‘rsatadi:

\[ \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 bo‘lakli tuzilish tasodifiy emas. Sikl cho‘qqilari va markaz cho‘qqilar bir vaqtning o‘zida nechta himoyasiz qo‘shnini himoya qilishi kerakligi \(m\) va \(t\) paritetiga qarab optimal kuchli cho‘qqi joylashuvini o‘zgartiradi.

Toj grafi

Toj grafi \(C(n)\), \(K_{n,n}\) dan mukammal moslik chiqarib tashlash orqali olinadi va jami \(2n\) cho‘qqini o‘z ichiga oladi. Manba quyidagi aniq qiymatni beradi:

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

Toq \(n\) da umumiy quyi chegara bilan konstruktiv yuqori chegara ustma-ust tushib, \(n+1\) ni beradi. Juft \(n\) da optimal yechimda ikki xil ikki bo‘lakli sinfda kuchli cho‘qqi bo‘lishi kerakligi ko‘rsatilib, quyi chegara \(n+2\) ga ko‘tariladi.

PDFning 4-rasmi \(C(3)\) toj grafida minimal kuchli Roma dominantlik funksiyasining misolini ko‘rsatadi.

Sikl-korona grafi \(C_m\circ K_1\)

Siklning har bir cho‘qqisiga bitta barg qo‘shilganda \(C_m\circ K_1\) grafi hosil bo‘ladi. Proposition 13 quyidagi aniq formulani beradi:

\[ \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} } \]

Yuqori chegara sikl cho‘qqilarida har to‘rtta cho‘qqida takrorlanadigan maxsus \(2,0,0,2\) ga o‘xshash yorliq tuzilishi va barg yorliqlaridan foydalanib quriladi. Quyi chegarada esa ayniqsa \(m\equiv0\pmod4\) holatda discharging, ya’ni yukni qayta taqsimlash argumenti qo‘llanadi.

Discharging usuli nima qiladi?

Isbotda dastlab har bir cho‘qqining yuki o‘z yorlig‘iga teng deb olinadi:

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

Keyin ayrim barglardan sikl cho‘qqilariga va 2 yorliqli sikl cho‘qqilaridan qo‘shnilariga yarim yoki bir to‘liq birlik yuk uzatiladi. Bu uzatish umumiy yukni o‘zgartirmaydi:

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

Biroq qayta taqsimlangan yuklar har bir sikl cho‘qqisida kamida \(3/2\) lik o‘rtacha hissa olish imkonini beradi. Natijada

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

quyi chegara kelib chiqadi va konstruktiv yuqori chegara bilan tenglashganda aniq qiymat isbotlanadi.

Maxsus tırtıl graflari

Umurtqa \(v_1,\ldots,v_n\) cho‘qqilaridan iborat bo‘lsin va har bir \(v_i\) ga

\[ x_i\geq2 \]

barg biriktirilgan bo‘lsin. Bu holda har bir umurtqa cho‘qqisi kuchli tayanch cho‘qqidir. Proposition 14:

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

aniq qiymatini beradi.

Yuqori chegara uchun har bir umurtqa cho‘qqisiga

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

yorlig‘i va barcha barglarga 0 yorlig‘i beriladi. Quyi chegara esa har bir kuchli tayanch cho‘qqi va uning barglari jami kamida shu og‘irlikni talab qilishi orqali olinadi.

PDFning 5-rasmi ushbu tuzilmani vizual tarzda ko‘rsatadi: umurtqadagi kuchli tayanch cho‘qqilar 2 yoki 3 kabi musbat yorliqlarni olib yurganda, ularga bog‘langan barglar 0 yorliqlidir. Rasmning vazifasi yopiq formuladagi har bir umurtqa cho‘qqining mahalliy hissasini ko‘rsatishdir.

Umumiyroq tırtıl grafi uchun yuqori chegara

Manba nihoyat umurtqada kuchli tayanch cho‘qqilar bilan birga \(k\) ta kuchsiz tayanch cho‘qqi va tayanch cho‘qqilar orasida tayanch bo‘lmagan cho‘qqilardan tashkil topgan \(q\) ta \(P_{r_j}\) qism yo‘l bo‘lishiga ruxsat beradi. Bu umumiyroq holatda aniq qiymat emas, quyidagi yuqori chegara beriladi:

\[ \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 } \]

Birinchi yig‘indi kuchli tayanch cho‘qqilarni va ularning barglarini, \(2k\) hadi kuchsiz tayanch cho‘qqilarni, oxirgi yig‘indi esa tayanch cho‘qqilar orasidagi oraliq yo‘llarning kuchli Roma dominantlik xarajatini ifodalaydi.

Manba rasmlarining ilmiy vazifalari

Tadqiqot qo‘llab-quvvatlaydigan xulosalar

Tadqiqot [k]-Roma dominantligini mos struktur graf sinflarida LinEMSOL va Courcelle doirasi orqali chiziqli-vaqt yechimiga keltirish mumkinligini; kuchli Roma dominantligi yulduz-konveks ikki bo‘lakli graflarda NP-to‘liq ekanini; shuningdek, muayyan ikki yulduz, yo‘l, sikl, g‘ildirak, toj, korona va tırtıl oilalarida dominantlik parametrlarini yopiq shaklda hisoblash mumkinligini matematik isbotlar bilan qo‘llab-quvvatlaydi.

Natijalar shuningdek, graf optimallashtirish masalasining murakkabligi faqat cho‘qqilar va qirralar soniga emas, balki grafning struktur sinfiga ham kuchli bog‘liq ekanini ko‘rsatadi: umumiy yoki ayrim ikki bo‘lakli sinflarda qaror masalasi qiyin bo‘lishi mumkin, cheklangan clique-width/treewidth tuzilishi esa qo‘shimcha algoritmik imkoniyat beradi.

Tadqiqot qo‘llab-quvvatlamaydigan xulosalar

Maqola real harbiy, logistika yoki infratuzilma tarmog‘ida tajriba o‘tkazmaydi. “Mudofaa birligi” tili graf nazariyasining tarixiy va konseptual talqinidir. Natijalar real dunyodagi resurs taqsimotiga bevosita samaradorlik kafolati bermaydi. LinEMSOL natijasi barcha graflarda chiziqli-vaqt algoritmi bor degani emas; u cheklangan clique-width va mos tasvir faraziga bog‘liq. NP-to‘liqlik natijasi ham har bir alohida graf misolini amalda yechib bo‘lmaydi degani emas; u masala sinfining eng yomon holatdagi hisoblash murakkabligini ifodalaydi.

Xuddi shuningdek, t-qavatli g‘ildirak, toj, korona va maxsus tırtıl graf formulalari faqat ko‘rsatilgan graf oilalari va parametr shartlari uchun amal qiladi; ixtiyoriy grafning kuchli Roma dominantlik sonini ushbu formulalardan chiqarib bo‘lmaydi.

Manbadagi ikki notatsiya muammosi

Birinchidan, kirish qismida \(P_n\), uzunligi \(n\) bo‘lgan va \(u_0,u_1,\ldots,u_n\) cho‘qqilaridan iborat yo‘l sifatida ta’riflansa, keyingi natijalarda \(P_n\), “tartibi \(n\)” bo‘lgan yo‘l ma’nosida ishlatiladi. Shu sababli ushbu Verianla matnida natijalar berilganda tegishli teorema yoki taklifning o‘zidagi “tartibi \(n\)” iborasi asos qilib olingan; kirishdagi ta’rif sukut bilan qayta yozilmagan.

Ikkinchidan, [k]-Roma reinforcement ta’rifida manba \(F\subseteq E(G)\) deb yozadi; biroq \(G+F\) ni qirra qo‘shish amali sifatida ta’riflaydi va Proposition 10 konstruksiyalarida yo‘lning mavjud qirrasi bo‘lmagan \(v_2v_4\), \(v_6v_8\), \(v_1v_3\) va \(v_1v_4\) qirralarini qo‘shadi. Ushbu ochiq manba-ichki nomuvofiqlik sababli Verianla ta’rifdagi to‘plam ifodasini taxmin asosida o‘zgartirmagan.

Manba va Usul Haqida Izoh

Asl tadqiqot: Complexity and Exact Values for [k]-Roman and Strong Roman Domination for Specific Graph Families

Mualliflar: 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.

Muassasalar: 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.

Nashriyot: MDPI.

Bibliografik yozuv: Mathematics 2026, 14(9), 1535.

DOI: 10.3390/math14091535.

Maqola jarayoni: Qabul qilindi 19 Fevral 2026; tahrir 6 Aprel 2026; qabul qilindi 28 Aprel 2026; nashr 1 May 2026.

Manba turi: Taqrizdan o‘tgan nazariy matematika / diskret matematika / graf nazariyasi tadqiqot maqolasi.

Litsenziya: Creative Commons Attribution (CC BY).

Ma’lumotlar holati: Mualliflar tadqiqotda yangi ma’lumotlar yaratilmagan yoki tahlil qilinmaganini bildiradi. Tadqiqotning isbot materiali graf tuzilmalari, matematik ta’riflar, teoremalar, takliflar va isbotlardan iborat.

Muallif hissalari: Konseptuallashtirish, metodologiya, tekshirish va tadqiqotga to‘rt muallifning barchasi hissa qo‘shgan. Dastlabki loyiha Martín Cera López va María Pilar Álvarez-Ruíz; ko‘rib chiqish va tahrirlash Juan Carlos Valenzuela-Tripodoro va María Antonia Mateos-Camacho tomonidan olib borilgan. Manba barcha mualliflar tadqiqotga teng hissa qo‘shganini ham alohida qayd etadi.

Moliyalashtirish: Juan Carlos Valenzuela-Tripodoro; Ispaniya Fan, Innovatsiya va Universitetlar vazirligining PID2022-139543OB-C41 loyihasi hamda Yevropa Komissiyasining Horizon Europe Marie Skłodowska-Curie Actions Staff Exchanges doirasidagi 101182819 raqamli COVER loyihasi tomonidan qisman qo‘llab-quvvatlangan. Martín Cera López; Andalusiya Mintaqaviy Hukumatining Tadqiqot, Rivojlanish va Innovatsiya Rejasi doirasidagi FQM-240 loyihasi va PPIT-FEDER SOL2024-31708 “Mathematics for Cybersecurity and Smart City Development” loyihasidan qisman yordam olgan.

Manfaatlar to‘qnashuvi: Mualliflar manfaatlar to‘qnashuvini bildirmagan.

Manba tuzilishi izohi: Maqolada alohida “Conclusions” bo‘limi yo‘q. Asosiy ilmiy mazmun Proposition 15 bilan tugagach, muallif hissalari, moliyalashtirish, ma’lumotlar mavjudligi va manfaatlar to‘qnashuvi bayonotlari keladi. Shu sababli Verianladagi “tadqiqot qo‘llab-quvvatlaydigan / qo‘llab-quvvatlamaydigan” baholar faqat maqoladagi isbotlangan natijalardan chiqarilgan; manbaga tegishli bo‘lmagan yangi xulosa bo‘limi sifatida taqdim etilmagan.

Asosiy metodologik chegara: Tadqiqot eksperimental yoki empirik emas. Algoritmik murakkablik natijalari ko‘rsatilgan graf sinfi va tasvir farazlariga; aniq-qiymat formulalari esa tegishli graf oilalari, paritet va kongruensiya shartlariga bog‘liq.

Notatsiya chegarasi: Manbadagi \(P_n\) uzunlik/tartib qo‘llanishi bilan reinforcement ta’rifidagi \(F\subseteq E(G)\) ifodasi manbada ko‘ringanidek ichki nomuvofiqlikka ega. Ushbu Verianla matni bu nuqtalarni yashirmagan va noma’lum tuzatishni manba natijasi sifatida taqdim etmagan.

Vizualni qayta chizish mosligi: Mos. Besh manba rasmning barchasi graf-nazariy sxema bo‘lgani uchun tugun joylashuvi va yorliqlash mantig‘i saqlangan holda Verianla uchun original vektor graf sxemalari yaratilishi mumkin. Maqsad pikselni nusxalash emas, balki ayni matematik munosabatni yangi dizayn bilan ko‘rinadigan qilishdir.

Verianla Live / Live Figure: Qisman mos. Ayniqsa 1–2-rasmlarda yorliqlar mudofaa shartini qanday qanoatlantirishini bosqichma-bosqich ajratib ko‘rsatish va 3-rasmda RX3C dan \(\Gamma(I)\) ga o‘tishni bosqichma-bosqich ko‘rsatish source-derived Live Figure sifatida qimmatlidir. Foydalanuvchiga grafni yoki \(k\) qiymatini o‘zgartirib yangi optimal natija hosil qilishga ruxsat berilmasligi kerak; bu manbada bajarilmagan yangi hisoblash bo‘ladi.