Доминацияи Римӣ модели оптимизатсионии граф аст, ки ба қуллаҳои граф тамғаҳои бутун медиҳад, онҳоро ҳамчун захираҳои дифоӣ тафсир мекунад, ҳифзи ҳамаи қуллаҳоро дар шароити муайяни ҳамсоягӣ таъмин менамояд ва ҳамзамон вазни умумии тамғаҳоро ҳадди ақал мекунад. Таҳқиқоти Juan Carlos Valenzuela-Tripodoro, María Antonia Mateos-Camacho, Martín Cera López ва María Pilar Álvarez-Ruíz ду шакли пешрафтаи ин модел — доминацияи [k]-Римӣ ва доминацияи Римии қавӣ — ро ҳам аз ҷиҳати мураккабии ҳисоббарорӣ ва ҳам аз ҷиҳати қиматҳои дақиқи параметрҳо дар баъзе оилаҳои граф меомӯзад.

Дар бахши доминацияи [k]-Римӣ муаллифон масъаларо дар шакли Linear Extended Monadic Second-Order Logic (LinEMSOL) ифода мекунанд. Дар натиҷа, агар намоиши мувофиқи граф мавҷуд бошад, масъала дар синфҳои дорои clique-width маҳдуд нисбат ба тартиби граф дар вақти хаттӣ ҳал мешавад. Дар бахши доминацияи Римии қавӣ бошад, NP-пурра будани масъалаи қарор дар графҳои дуқисмии ситора-конвекс бо коҳиш аз масъалаи Restricted Exact 3-Cover нишон дода мешавад.

Самти дуюми асосии таҳқиқот қиматҳои дақиқ аст. Барои ситораҳои дугона, баъзе роҳҳо ва даврҳо, чархҳои t-қабата, графҳои тоҷ, ҳосили коронаи давр бо як қулла ва баъзе синфҳои графи кирммонанд ададҳои доминацияи [k]-Римӣ ё Римии қавӣ муайян карда мешаванд. Натиҷаҳо таҷрибавӣ нестанд; онҳо ба тамғагузории граф, ҳудудҳои поёнӣ ва болоии комбинаторӣ, ифодашавии мантиқӣ, коҳишҳои мураккабӣ ва исботҳои конструктивӣ такя мекунанд.

Доминацияи Римӣ чист?

Доминацияи Римӣ модели оптимизатсионии тамғагузории қуллаҳо мебошад, ки ба қуллаҳои граф тамғаҳои 0, 1 ё 2 медиҳад ва талаб мекунад, ки ҳар қуллаи дорои тамғаи 0 ҳадди ақал як ҳамсояи дорои тамғаи 2 дошта бошад; ҳадаф кам кардани вазни умумии ҳамаи тамғаҳост.

Графи сода, бесамт ва ниҳоӣ

\[ G=(V,E) \]

бо ин ишора карда шавад. Дар ин ҷо \(V\) маҷмӯи қуллаҳо ва \(E\) маҷмӯи канорҳоро ифода мекунад. Функсияи классикии доминацияи Римӣ

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

шакл дорад. Агар \(f(v)=0\) бошад, барои ҳадди ақал як ҳамсояи \(v\) аз \(u\)

\[ f(u)=2 \]

бояд иҷро шавад.

Вазни функсия

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

мебошад. Адади доминацияи Римии граф

\[ \gamma_R(G) \]

камтарин вазн дар байни ҳамаи функсияҳои эътиборноки доминацияи Римӣ аст.

Номи “Рим” аз ташбеҳи таърихии дифоӣ меояд: дар ҷойе бо тамғаи 0 воҳиди мустақими дифоӣ нест; аммо агар дар ҷойи ҳамсоя ду воҳид бошад, он ҳамсоя метавонад як воҳидро бе аз даст додани тамоми дифои худ ба кӯмак фиристад. Аз нигоҳи математикӣ муҳим қиссаи таърихӣ нест, балки оптимизатсияи ҳамзамони шартҳои маҳаллии ҳифз дар граф ва арзиши умумии захираҳо мебошад.

Ҳамсоягӣ ва ҳамсоягии фаъол

Ҳамсоягии кушодаи қуллаи \(u\), яъне \(N(u)\), маҷмӯи қуллаҳое мебошад, ки ба \(u\) пайвастанд. Ҳамсоягии пӯшида бошад

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

таъриф мешавад.

Ҳангоми дода шудани тамғагузории \(f\), ҳамсоягии фаъол

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

мебошад. Ин мафҳум махсусан дар таърифи доминацияи [k]-Римӣ нақши марказӣ дорад.

Доминацияи [k]-Римӣ аз модели классикӣ чӣ фарқ дорад?

Доминацияи [k]-Римӣ иҷозат медиҳад, ки ба ҳар қулла тамғае байни \(0\) ва \(k+1\) дода шавад ва бо талаб кардани он ки ҷамъи тамғаҳо дар ҳамсоягии пӯшидаи ҳар қулла ҳадди ақал ба \(k\) плюс шумораи ҳамсояҳои фаъол баробар бошад, доминацияи классикии Римиро ба модели умумитарини тақсимоти захираҳо табдил медиҳад.

Функсияи доминацияи [k]-Римӣ, кӯтоҳаш [k]-RDF,

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

таъриф мешавад ва барои ҳар \(u\in V\)

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

шартро бояд қонеъ кунад.

Дар ин ҷо

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

ҷамъи тамғаҳо дар ҳамсоягии пӯшида аст. \(|AN(u)|\) шумораи ҳамсояҳои фаъоли \(u\) мебошад, ки тамғаи мусбат доранд. Бинобар ин ҷамъи ҳадди ақали зарурӣ на танҳо ба \(k\), балки ба шумораи қуллаҳои фаъол дар атрофи қулла низ вобаста аст.

Вазни ҳадди ақали доминацияи [k]-Римӣ дар граф

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

ишора мешавад.

Шакли 1-и манбаъ дар як граф тамғагузории классикии доминацияи Римӣ ва тамғагузории [k]-Римиро паҳлу ба паҳлу нишон медиҳад. Дар мисол қимати классикӣ

\[ \gamma_R(G)=6 \]

аст, дар ҳоле ки қимати нишон додашудаи [k]-Римӣ

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

мебошад. Инҳо формулаҳои умумӣ барои ҳамаи графҳо нестанд, балки қиматҳое мебошанд, ки тамғагузории графи мушаххаси Шакли 1-ро шарҳ медиҳанд.

Доминацияи Римии қавӣ чиро модел мекунад?

Доминацияи Римии қавӣ варианти доминацияи Римӣ аст, ки барои модел кардани ҳифзи ҳамзамони чанд ҳамсояи муҳофизатнашуда ба ҷои як ҳамла, талаб мекунад қуллаи қавии дорои тамғаи мусбат вазни дифоие дошта бошад, ки ба ҳадди ақал нисфи ҳамсояҳои дорои тамғаи 0-и он кифоя кунад.

Дараҷаи максималии граф \(\Delta\) бошад. Функсияи доминацияи Римии қавӣ, кӯтоҳаш StRDF, қуллаҳоро аз маҷмӯи

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

тамғагузорӣ мекунад.

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

маҷмӯи қуллаҳои дорои тамғаи 0 бошад; барои ҳар \(v\in B_0\) бояд як ҳамсояи \(u\) мавҷуд бошад ва

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

шарт иҷро шавад.

Дар ин формула \(|N(u)\cap B_0|\) шумораи ҳамсояҳои дорои тамғаи 0-и муҳофиз \(u\) мебошад. Аъзои 1 дар тарафи рост муҳофизати худи муҳофизро ва аъзои дуюме, ки бо функсияи сақф ҳисоб мешавад, иқтидори иловагии лозим барои ҳамсояҳои муҳофизатнашудаеро ифода мекунад, ки ӯ метавонад ҳамзамон ҳимоя кунад.

Адади доминацияи Римии қавӣ

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

ишора мешавад.

Дар Шакли 2-и манбаъ барои ҳамон графи намунавӣ вазни доминацияи классикии Римӣ 6 ва вазни доминацияи Римии қавӣ 8 нишон дода шудааст. Ин тасвир барои фаҳмондани он истифода шудааст, ки шарти чанд ҳамлаи ҳамзамон метавонад дар ҳамон граф вазни умумии дифоии бештар талаб кунад.

Ҳудудҳои умумии поёнӣ ва болоӣ

Манбаъ се ҳуди асосии пештар маълумро истифода мебарад. Аввал

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

дода мешавад; дар ин ҷо \(\gamma(G)\) адади классикии доминация аст.

Барои графи тартибаш \(n\) инчунин

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

ҳуди болоӣ ва

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

ҳуди поёнӣ истифода мешаванд. Ин ҳудудҳо дар исботҳои минбаъдаи қиматҳои дақиқ барои ба як қимат расондани ҳуди болоии аз тамғагузории конструктивӣ ҳосилшуда ва ҳуди поёнии маҷбурӣ кӯмак мекунанд.

Чаро оилаҳои граф муҳиманд?

Ҳалли масъалаи умумии оптимизатсионӣ дар ҳамаи графҳо метавонад душвор бошад; аммо дар оилаҳои сохтории махсус, ба мисли дарахтҳо, роҳҳо, даврҳо, графҳои дуқисмӣ ё синфҳои дорои clique-width маҳдуд натиҷаҳои алгоритмӣ ва шакли пӯшидаи қавитар ба даст овардан мумкин аст. Равиши асосии ин таҳқиқот низ дуҷониба аст: муайян кардани он ки масъалаи умумӣ дар кадом сохторҳо аз ҷиҳати ҳисоббарорӣ осон ё душвор аст ва ҳисоб кардани вазни оптималӣ дар баъзе оилаҳои граф мустақиман бо формула.

Баъзе оилаҳои графи истифодашуда дар таҳқиқот

Усул ва Натиҷаҳои Таҳқиқот

Доминацияи [k]-Римӣ дар кадом синфҳои граф дар вақти хаттӣ ҳал мешавад?

Азбаски доминацияи [k]-Римӣ метавонад ҳамчун масъалаи оптимизатсионии LinEMSOL ифода шавад, дар синфи графҳои дорои clique-width маҳдуд, агар \(r\)-ифодаи мувофиқ бо вуруд дода шавад ё самаранок сохта шавад, функсияи минималии доминацияи [k]-Римӣ нисбат ба тартиби граф дар вақти хаттӣ муайян мешавад.

Равиши MSOL ва LinEMSOL

Мантиқи Монадикии Тартиби Дуюм, яъне MSOL, имкон медиҳад на танҳо бар қуллаҳои алоҳида, балки бар маҷмӯи қуллаҳо низ кванторгузорӣ карда шавад. Агар муносибати ҳамсоягии граф бо

\[ R(u,v) \]

ифода шавад, бисёр хусусиятҳои комбинаториро бо формулаҳои мантиқӣ муайян кардан мумкин аст.

LinEMSOL ин сохторро бо функсияҳои хаттии ҳадаф, ки аз кардиналияти маҷмӯаҳои монадӣ сохта мешаванд, васеъ мекунад. Дар мақола тамғагузории [k]-Римӣ

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

ба маҷмӯи қуллаҳо ҷудо мешавад; \(V_j\) маҷмӯи қуллаҳои дорои қимати тамғаи \(j\) мебошад.

Аз ҷиҳати мантиқӣ ифода мешавад, ки ин маҷмӯаҳо partition-и \(V\)-ро ташкил мекунанд ва ҳар қулла шарти [k]-RDF-ро қонеъ мекунад. Ҳадафи оптимизатсия

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

мебошад.

Ин ифода вазни тамғаро мустақиман ҳадди ақал мекунад. Бо равиши Courcelle масъала, агар таҷзия/намоиши мувофиқ вуҷуд дошта бошад, метавонад дар синфҳои дорои clique-width маҳдуд ба алгоритми вақти хаттӣ табдил дода шавад.

Дар Corollary 2-и манбаъ натиҷа дар шакли \(f(k)\cdot n\) дода мешавад ва cographs, distance-hereditary graphs, complete graphs, trees, series-parallel graphs ва outerplanar graphs ҳамчун синфҳои намунавӣ номбар мешаванд.

Чаро доминацияи Римии қавӣ NP-пурра аст?

Таҳқиқот NP-пурра будани масъалаи қарори доминацияи Римии қавиро дар графҳои дуқисмии ситора-конвекс бо сохтани графи мушаххаси дуқисмии ситора-конвекс аз як намунаи Restricted Exact 3-Cover ва баробарқувват кардани мавҷудияти exact cover бо мавҷудияти тамғагузории Римии қавии вазни кам исбот мекунад.

Масъалаи қарор

Ҳамчун вуруд як

\[ G=(V,E) \]

граф ва адади бутуни мусбати \(k\) дода мешавад. Савол чунин аст:

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

Азбаски шартҳои StRDF ва ҳуди вазни як тамғагузории номзадро дар вақти полиномӣ санҷидан мумкин аст, масъала дар NP қарор дорад.

Коҳиш аз RX3C

Дар масъалаи Restricted Exact 3-Cover

\[ |X|=3q \]

ва \(C\) оилаи зермаҷмӯаҳои сеэлемента мебошад; ҳар \(x\in X\) маҳз дар се маҷмӯи гуногун ҷой дорад. Савол ин аст, ки оё оилаи \(X\), ки \(C^\ast\subseteq C\)-ро бидуни буриш пурра мепӯшонад, вуҷуд дорад.

Манбаъ аз ин намуна графи дуқисмии ситора-конвекси \(\Gamma(I)\)-ро месозад ва ҳадди вазни доминацияи Римии қавиро

\[ 6q+2 \]

интихоб мекунад.

Дар сохтмон синфҳои дуқисмӣ

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

мебошанд. Бинобар ин

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

Қуллаи \(x_i\) танҳо ва танҳо вақте ба \(c_j\) пайваст мешавад, ки элементи мувофиқ дар маҷмӯи сегонаи мувофиқ бошад. Илова бар ин, \(a\) ба ҳамаи қуллаҳои \(c_j\) ва ба \(a_1,a_2\), ва ҳар \(c_j\) ба \(z_j\)-и худ пайваст мешавад.

Шакли 3-и PDF каркаси ин графи коҳишро нишон медиҳад. Вазифаи илмии шакл намоён сохтани он аст, ки узвияти маҷмӯи RX3C чӣ гуна ба сохтори ҳамсоягии граф рамзгузорӣ мешавад.

Дар самти пеши исбот, агар exact cover \(C'\) мавҷуд бошад, ба қуллаҳои интихобшудаи \(c_j\) тамғаи 3, ба баъзе қуллаҳои \(z_i\) тамғаи 1 ва ба маркази \(a\) тамғаи \(q+2\) дода мешавад ва функсияи доминацияи Римии қавӣ бо вазни умумии

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

сохта мешавад.

Дар самти баръакс, сохтори як StRDF-и оптималӣ бо вазни на бештар аз \(6q+2\) қадам ба қадам маҳдуд карда мешавад ва нишон дода мешавад, ки маҳз \(q\) қуллаи \(c_j\) бояд тамғаи 3 дошта бошанд ва онҳо exact cover-и \(X\)-ро ташкил диҳанд. Ҳамин тавр ҷавоби “ҳа”-и намунаи RX3C ба ҷавоби “ҳа”-и намунаи StRDN баробарқувват мешавад.

Қуллаҳои такягоҳӣ дар доминацияи [k]-Римӣ

Lemma 1-и манбаъ рафтори баргҳо ва қуллаҳои такягоҳиро дар тамғагузории оптималӣ маҳдуд мекунад. Барои \(k\geq2\), қуллаи такягоҳии заифи \(v\) ва барги \(u\), ки ба он пайваст аст,

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

Агар ҷамъи онҳо маҳз \(k\) бошад, ҳатман

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

Барои қуллаи такягоҳии қавии \(v\), яъне қуллае, ки ба ҳадди ақал ду барг ҳамсоя аст, дар тамғагузории оптималии [k]-Римӣ

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

ва дар ҳамаи баргҳои пайваст ба \(v\)

\[ f(u)=0 \]

будан нишон дода мешавад. Ин лемма санги асосии натиҷаҳои минбаъдаи дарахт ва ситораи дугона аст.

Дар доминацияи [k]-Римӣ кадом қиматҳои дақиқ ба даст омаданд?

Таҳқиқот барои ситораҳои дугона формулаҳои мустақим, барои роҳҳо ва даврҳо ҳангоми \(n\equiv0\pmod3\) шакли пӯшидаи умумӣ ва барои адади reinforcement-и [k]-Римии роҳҳо натиҷаҳои вобаста ба синфҳои конгруэнтӣ медиҳад.

Ситораҳои дугона

Агар \(S_{1,q}\) ситораи дугонае бошад, ки як қуллаи такягоҳии заиф ва як қуллаи такягоҳии қавӣ дорад,

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

ба даст меояд.

Агар ҳар ду марказ ҳадди ақал ду барг дошта бошанд, яъне барои \(p,q\geq2\)

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

Сохтори паси формулаи дуюм сода аст: ҳар ду марказ қуллаҳои такягоҳии қавӣ мебошанд ва мувофиқи Lemma 1 ҳар кадом вазни \(k+1\) доранд; тамғаи оптималии баргҳо 0 аст.

Сохтори тамғаҳо дар роҳҳо ва даврҳо

Манбаъ нишон медиҳад, ки дар роҳ ё даври дорои ҳадди ақал чор қулла, дар функсияи минималии [k]-Римӣ баъзе тамғаҳои сатҳи миёна наметавонанд дар чор қуллаи пайдарпай беист такрор шаванд. Вақте \(k\) ҷуфт аст, сохтори мамнӯъ то се қуллаи пайдарпай қавитар мешавад.

Ин гуна маҳдудиятҳои маҳаллии сохторӣ барои фаҳмидани он ки тамғаҳои оптималӣ кадом намунаҳои давриро метавонанд ташкил диҳанд ва барои ҳосил кардани қиматҳои дақиқ кӯмак мекунанд.

Муқоисаи роҳ ва давр

Азбаски даврро бо илова кардани як канор ба роҳи ҳамон тартиб ба даст овардан мумкин аст, манбаъ нобаробарии

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

ро медиҳад.

Агар дар як тамғагузории оптималии муайяни роҳ шартҳои \(V_1=\varnothing\) ва \(V_{k+1}=\varnothing\) иҷро шаванд, натиҷаи қавитар

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

ба даст меояд.

Қимати дақиқ дар ҳолати \(n\equiv0\pmod3\)

Агар \(n\) ба се тақсим шавад, ҳам барои \(P_n\) ва ҳам барои \(C_n\) маҷмӯи самараноки доминантиро ҳар се қулла якто интихоб кардан мумкин аст. Дар ин ҳолат

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

мешавад.

Дар ин ҷо ҳар қуллаи доминантии интихобшуда вазни \(k+1\) дорад ва ҳамсоягиҳои пӯшида графро бе ҳампӯшӣ мепӯшонанд.

Reinforcement дар графҳои роҳ

Манбаъ адади reinforcement-и [k]-Римиро бо \(r_{[kR]}(G)\) ишора мекунад ва ҳамчун ҳадафи асосӣ меомӯзад, ки барои кам кардани адади доминацияи [k]-Римии граф чанд канори нав кофӣ аст.

Огоҳии нотационӣ дар дохили манбаъ: Дар Definition 1 \(F\subseteq E(G)\) навишта шудааст; аммо ҳамон таъриф \(G+F\)-ро ҳамчун “илова кардани канорҳои дар \(F\)” шарҳ медиҳад ва дар исботи баъдӣ канорҳое илова мешаванд, ки дар роҳи ибтидоӣ вуҷуд надоштанд. Аз ин рӯ, дар ин ҷо ифодаи чопшудаи таъриф хомӯшона тағйир дода нашудааст ва натиҷаҳо аз рӯи сохтмонҳои ошкори Proposition 10 оварда шудаанд.

Барои \(n\geq4\) манбаъ

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

натиҷаро медиҳад.

Қиматҳои роҳ, ки дар исбот истифода мешаванд, мутаносибан

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

ва

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

мебошанд.

Барои кадом оилаҳои граф дар доминацияи Римии қавӣ формулаҳои дақиқ ёфт шуданд?

Таҳқиқот барои чархҳои \(t\)-қабата, графҳои тоҷ, графҳои коронаи \(C_m\circ K_1\) ва баъзе графҳои кирммонанд, ки дар ҳар қуллаи сутунмӯҳра ҳадди ақал ду барг доранд, адади доминацияи Римии қавиро пурра муайян мекунад; барои графҳои кирммонанди умумитар бошад ҳуди болоӣ медиҳад.

Чархҳои \(t\)-қабата

\(W_{m,t}\) бо пайваст кардани \(C_m\) қуллаи марказии ба ҳам нопайваст ба як даври \(t\) сохта мешавад. Proposition 11 нишон медиҳад, ки адади доминацияи Римии қавӣ вобаста ба андоза ва шартҳои паритетии \(m\) ва \(t\) тағйир меёбад:

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

Ин сохтори қисмбандӣ тасодуфӣ нест. Он ки қуллаҳои давр ва қуллаҳои марказӣ бояд чанд ҳамсояи муҳофизатнашударо ҳамзамон ҳимоя кунанд, вобаста ба паритети \(m\) ва \(t\) ҷойгиршавии оптималии қуллаҳои қавиро тағйир медиҳад.

Графи тоҷ

Графи тоҷ \(C(n)\) бо хориҷ кардани як мувофиқати комил аз \(K_{n,n}\) ҳосил мешавад ва дар маҷмӯъ \(2n\) қулла дорад. Манбаъ қимати дақиқи зеринро медиҳад:

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

Барои \(n\)-и тоқ ҳуди умумии поёнӣ ва ҳуди конструктивии болоӣ яксон шуда, \(n+1\)-ро медиҳад. Барои \(n\)-и ҷуфт нишон дода мешавад, ки дар ҳалли оптималӣ бояд дар ду синфи гуногуни дуқисмӣ қуллаи қавӣ мавҷуд бошад ва ҳуди поёнӣ то \(n+2\) боло бурда мешавад.

Шакли 4-и PDF намунаи функсияи минималии доминацияи Римии қавиро дар графи тоҷи \(C(3)\) нишон медиҳад.

Графи давр-корона \(C_m\circ K_1\)

Вақте ба ҳар қуллаи давр як барг илова мешавад, графи \(C_m\circ K_1\) ҳосил мегардад. Proposition 13 формулаи дақиқи зеринро медиҳад:

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

Ҳуди болоӣ бо истифода аз сохтори махсуси тамғаҳо монанди \(2,0,0,2\), ки дар ҳар чор қуллаи давр такрор мешавад, ва тамғаҳои баргҳо сохта мешавад. Дар ҳуди поёнӣ махсусан барои ҳолати \(m\equiv0\pmod4\) аз усули discharging, яъне бозтақсимкунии бор, истифода мешавад.

Усули discharging чӣ мекунад?

Дар исбот дар оғоз бори ҳар қулла баробари тамғаи худи он гирифта мешавад:

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

Сипас аз баъзе баргҳо ба қуллаҳои давр ва аз қуллаҳои даври дорои тамғаи 2 ба ҳамсояҳояшон ним ё як воҳиди пурраи бор интиқол дода мешавад. Ин интиқол бори умумиро тағйир намедиҳад:

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

Аммо борҳои бозтақсимшуда имкон медиҳанд, ки барои ҳар қуллаи давр ҳадди ақал саҳми миёнаи \(3/2\) ба даст ояд. Дар натиҷа

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

ҳуди поёнӣ ҳосил мешавад ва вақте бо ҳуди конструктивии болоӣ баробар мешавад, қимати дақиқ исбот мегардад.

Графҳои махсуси кирммонанд

Бигзор сутунмӯҳра аз қуллаҳои \(v_1,\ldots,v_n\) иборат бошад ва ба ҳар \(v_i\)

\[ x_i\geq2 \]

барг пайваст бошад. Дар ин ҳолат ҳар қуллаи сутунмӯҳра қуллаи такягоҳии қавӣ аст. Proposition 14:

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

қимати дақиқро медиҳад.

Барои ҳуди болоӣ ба ҳар қуллаи сутунмӯҳра

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

тамға ва ба ҳамаи баргҳо тамғаи 0 дода мешавад. Ҳуди поёнӣ аз он ҳосил мешавад, ки ҳар қуллаи такягоҳии қавӣ ва баргҳои он дар маҷмӯъ ҳадди ақал ҳамин вазнро талаб мекунанд.

Шакли 5-и PDF ин сохторро ба таври визуалӣ нишон медиҳад: қуллаҳои такягоҳии қавӣ дар сутунмӯҳра тамғаҳои мусбати 2 ё 3 доранд, дар ҳоле ки баргҳои пайваст тамғаи 0 доранд. Нақши шакл намоён кардани саҳми маҳаллии ҳар қуллаи сутунмӯҳра дар формулаи пӯшида аст.

Ҳуди болоӣ барои графи кирммонанди умумитар

Дар охир манбаъ иҷозат медиҳад, ки дар сутунмӯҳра илова ба қуллаҳои такягоҳии қавӣ \(k\) қуллаи такягоҳии заиф ва байни қуллаҳои такягоҳӣ \(q\) зерроҳи \(P_{r_j}\), ки аз қуллаҳои ғайритакягоҳӣ иборатанд, мавҷуд бошанд. Дар ин ҳолати умумитар на қимати дақиқ, балки ҳуди болоии зерин дода мешавад:

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

Ҷамъи аввал қуллаҳои такягоҳии қавӣ ва баргҳои онҳоро, аъзои \(2k\) қуллаҳои такягоҳии заиф ва ҷамъи охирин арзиши доминацияи Римии қавии роҳҳои мобайни қуллаҳои такягоҳиро ифода мекунад.

Вазифаҳои илмии шаклҳои манбаъ

Натиҷаҳое, ки таҳқиқот дастгирӣ мекунад

Таҳқиқот бо исботҳои математикӣ дастгирӣ мекунад, ки доминацияи [k]-Римиро дар синфҳои сохтории мувофиқи граф тавассути чорчӯбаи LinEMSOL ва Courcelle ба ҳалли вақти хаттӣ овардан мумкин аст; доминацияи Римии қавӣ дар графҳои дуқисмии ситора-конвекс NP-пурра аст; инчунин параметрҳои доминацияро дар баъзе оилаҳои ситораи дугона, роҳ, давр, чарх, тоҷ, корона ва кирммонанд дар шакли пӯшида ҳисоб кардан мумкин аст.

Натиҷаҳо инчунин нишон медиҳанд, ки мураккабии масъалаи оптимизатсионии граф на танҳо ба шумораи қуллаҳо ва канорҳо, балки ба синфи сохтории граф низ сахт вобаста аст: масъалаи қарор дар синфҳои умумӣ ё баъзе синфҳои дуқисмӣ метавонад душвор бошад, дар ҳоле ки сохтори clique-width/treewidth маҳдуд фишанги алгоритмии иловагӣ медиҳад.

Натиҷаҳое, ки таҳқиқот дастгирӣ намекунад

Мақола дар шабакаи воқеии ҳарбӣ, логистикӣ ё инфрасохторӣ таҷриба намегузаронад. Забони “воҳиди дифоӣ” тафсири таърихӣ ва консептуалии назарияи граф аст. Натиҷаҳо барои тақсимоти захираҳо дар ҷаҳони воқеӣ кафолати мустақими самаранокӣ намедиҳанд. Натиҷаи LinEMSOL маънои онро надорад, ки барои ҳамаи графҳо алгоритми вақти хаттӣ вуҷуд дорад; он ба clique-width маҳдуд ва фарзияи намоиши мувофиқ вобаста аст. Натиҷаи NP-пуррагӣ низ маънои онро надорад, ки ҳар як намунаи алоҳидаи граф дар амал ҳалнашаванда аст; он мураккабии ҳисоббарории ҳолати бадтарини синфи масъалаҳоро ифода мекунад.

Ба ҳамин монанд, формулаҳои чархи t-қабата, тоҷ, корона ва графи махсуси кирммонанд танҳо барои оилаҳои граф ва шартҳои параметрии зикршуда дурустанд; адади доминацияи Римии қавии графи ихтиёриро аз ин формулаҳо баровардан мумкин нест.

Ду масъалаи нотационӣ дар манбаъ

Аввал, дар бахши муқаддима \(P_n\) ҳамчун роҳи дарозиаш \(n\), ки аз қуллаҳои \(u_0,u_1,\ldots,u_n\) иборат аст, таъриф мешавад, аммо дар натиҷаҳои баъдӣ \(P_n\) ба маънои роҳи “тартибаш \(n\)” истифода мешавад. Аз ин рӯ, дар ин матни Verianla ҳангоми интиқоли натиҷаҳо ифодаи худи теорема ё пешниҳоди мувофиқ — “тартиб \(n\)” — асос гирифта шудааст; таърифи муқаддима хомӯшона аз нав навишта нашудааст.

Дуюм, дар таърифи reinforcement-и [k]-Римӣ манбаъ \(F\subseteq E(G)\) менависад; аммо \(G+F\)-ро ҳамчун амали илова кардани канор таъриф мекунад ва дар конструксияҳои Proposition 10 канорҳои \(v_2v_4\), \(v_6v_8\), \(v_1v_3\) ва \(v_1v_4\)-ро, ки дар роҳи аслӣ вуҷуд надоранд, илова мекунад. Аз сабаби ин номувофиқии ошкори дохилии манбаъ, Verianla ифодаи маҷмӯавии таърифро бар асоси тахмин тағйир надодааст.

Ёддошт оид ба Манбаъ ва Усул

Таҳқиқоти аслӣ: Complexity and Exact Values for [k]-Roman and Strong Roman Domination for Specific Graph Families

Муаллифон: 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.

Муассисаҳо: 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.

Маҷалла: Mathematics.

Ношир: MDPI.

Сабти библиографӣ: Mathematics 2026, 14(9), 1535.

DOI: 10.3390/math14091535.

Раванди мақола: Қабул 19 Феврал 2026; бознигарӣ 6 Апрел 2026; қабул 28 Апрел 2026; нашр 1 Май 2026.

Навъи манбаъ: Мақолаи таҳқиқотии рецензияшуда дар математикаи назариявӣ / математикаи дискретӣ / назарияи граф.

Иҷозатнома: Creative Commons Attribution (CC BY).

Ҳолати додаҳо: Муаллифон мегӯянд, ки дар таҳқиқот додаҳои нав эҷод ё таҳлил нашудаанд. Маводи исботии таҳқиқот аз сохторҳои граф, таърифҳои математикӣ, теоремаҳо, пешниҳодҳо ва исботҳо иборат аст.

Саҳми муаллифон: Ҳар чор муаллиф дар консептуализатсия, методология, санҷиш ва таҳқиқот саҳм гузоштаанд. Лоиҳаи аввал аз ҷониби Martín Cera López ва María Pilar Álvarez-Ruíz; баррасӣ ва таҳрир аз ҷониби Juan Carlos Valenzuela-Tripodoro ва María Antonia Mateos-Camacho анҷом дода шудааст. Манбаъ инчунин алоҳида қайд мекунад, ки ҳамаи муаллифон ба таҳқиқот баробар саҳм гузоштаанд.

Маблағгузорӣ: Juan Carlos Valenzuela-Tripodoro; қисман аз ҷониби лоиҳаи PID2022-139543OB-C41-и Вазорати Илм, Инноватсия ва Донишгоҳҳои Испания ва лоиҳаи COVER бо рақами 101182819 дар доираи Horizon Europe Marie Skłodowska-Curie Actions Staff Exchanges-и Комиссияи Аврупо дастгирӣ шудааст. Martín Cera López; аз лоиҳаи FQM-240 дар доираи Нақшаи Таҳқиқот, Рушд ва Инноватсияи Ҳукумати Минтақавии Андалусия ва лоиҳаи PPIT-FEDER SOL2024-31708 “Mathematics for Cybersecurity and Smart City Development” қисман дастгирӣ гирифтааст.

Бархӯрди манфиатҳо: Муаллифон бархӯрди манфиатҳоро гузориш накардаанд.

Ёддошти сохтори манбаъ: Дар мақола бахши ҷудогонаи “Conclusions” вуҷуд надорад. Пас аз анҷоми мундариҷаи асосии илмӣ бо Proposition 15, саҳми муаллифон, маблағгузорӣ, дастрасии додаҳо ва изҳороти бархӯрди манфиатҳо меоянд. Аз ин рӯ, арзёбиҳои “таҳқиқот дастгирӣ мекунад / дастгирӣ намекунад” дар Verianla танҳо аз натиҷаҳои исботшудаи мақола ҳосил шудаанд; онҳо ҳамчун бахши нави натиҷа, ки ба манбаъ тааллуқ надорад, пешниҳод нашудаанд.

Ҳадди асосии методологӣ: Таҳқиқот таҷрибавӣ ё эмпирикӣ нест. Натиҷаҳои мураккабии алгоритмӣ ба синфи граф ва фарзияҳои намоишии зикршуда вобастаанд; формулаҳои қиматҳои дақиқ бошад ба оилаҳои мувофиқи граф, паритет ва шартҳои конгруэнтӣ вобастаанд.

Ҳадди нотационӣ: Истифодаи \(P_n\) аз ҷиҳати дарозӣ/тартиб ва ифодаи \(F\subseteq E(G)\) дар таърифи reinforcement, ҳамон тавре ки дар манбаъ омадааст, номувофиқии дохилӣ дорад. Ин матни Verianla ин нуктаҳоро пинҳон накардааст ва ислоҳи номаълумро ҳамчун натиҷаи манбаъ пешниҳод накардааст.

Мувофиқати бозкашии визуалӣ: Мувофиқ. Азбаски ҳамаи панҷ шакли манбаъ схемаҳои назарияи граф мебошанд, бо нигоҳ доштани ҷойгиршавии гиреҳҳо ва мантиқи тамғагузорӣ барои Verianla схемаҳои нави вектории граф сохтан мумкин аст. Ҳадаф нусхабардории пикселӣ нест, балки намоён кардани ҳамон муносибати математикӣ бо тарҳи нав мебошад.

Verianla Live / Live Figure: Қисман мувофиқ. Хусусан дар Шаклҳои 1–2 нишон додани пайдарпайи он ки тамғаҳо шарти дифоиро чӣ гуна қонеъ мекунанд ва дар Шакли 3 намоиши марҳила ба марҳилаи табдили RX3C ба \(\Gamma(I)\) ҳамчун source-derived Live Figure арзишманд аст. Ба корбар набояд иҷозат дода шавад, ки граф ё қимати \(k\)-ро иваз карда натиҷаи нави оптималӣ тавлид кунад; ин ҳисобкунии наве мебуд, ки дар манбаъ анҷом нашудааст.