Roma baskınlığı, bir grafın tepelerine savunma kaynağı gibi yorumlanabilen tamsayı etiketler atayıp bütün tepelerin belirli komşuluk koşulları altında korunmasını sağlarken toplam etiket ağırlığını en aza indirmeyi amaçlayan bir graf optimizasyon modelidir. Juan Carlos Valenzuela-Tripodoro, María Antonia Mateos-Camacho, Martín Cera López ve María Pilar Álvarez-Ruíz'in çalışması, bu modelin iki gelişmiş biçimini, [k]-Roma baskınlığı ile güçlü Roma baskınlığını, hem hesaplama karmaşıklığı hem de belirli graf ailelerindeki kesin parametre değerleri açısından inceliyor.

[k]-Roma baskınlığı tarafında yazarlar problemi Linear Extended Monadic Second-Order Logic (LinEMSOL) biçiminde ifade ediyor. Bunun sonucu olarak uygun graf gösterimi mevcut olduğunda sınırlı clique-width sınıflarında problem grafın mertebesine göre doğrusal zamanda çözülebiliyor. Güçlü Roma baskınlığı tarafında ise karar probleminin yıldız-konveks iki parçalı graflarda NP-tam olduğu, Restricted Exact 3-Cover probleminden yapılan bir indirgemeyle gösteriliyor.

Çalışmanın ikinci ana ekseni kesin değerlerdir. Çift yıldızlar, belirli yollar ve çevrimler, t-katlı çarklar, taç grafları, çevrim ile tek tepenin korona çarpımı ve belirli tırtıl graf sınıfları için [k]-Roma veya güçlü Roma baskınlık sayıları belirleniyor. Sonuçlar deneysel değildir; graf etiketlemeleri, kombinatoryal alt ve üst sınırlar, mantıksal ifade edilebilirlik, karmaşıklık indirgemeleri ve yapıcı ispatlara dayanır.

Roma baskınlığı nedir?

Roma baskınlığı, bir grafın tepelerine 0, 1 veya 2 etiketleri atayan ve 0 etiketli her tepenin en az bir 2 etiketli komşuya sahip olmasını zorunlu kılan bir tepe-etiketleme optimizasyon modelidir; amaç bütün etiketlerin toplam ağırlığını en aza indirmektir.

Basit, yönsüz ve sonlu bir graf

\[ G=(V,E) \]

ile gösterilsin. Burada \(V\) tepeler kümesini, \(E\) ise ayrıtlar kümesini ifade eder. Klasik Roma baskınlık fonksiyonu

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

şeklindedir. Eğer \(f(v)=0\) ise \(v\)'nin en az bir komşusu \(u\) için

\[ f(u)=2 \]

olması gerekir.

Fonksiyonun ağırlığı

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

şeklindedir. Grafın Roma baskınlık sayısı

\[ \gamma_R(G) \]

ise bütün geçerli Roma baskınlık fonksiyonları arasındaki en küçük ağırlıktır.

“Roma” adı tarihsel bir savunma benzetmesinden gelir: 0 etiketli bir konumda doğrudan savunma birimi bulunmaz; ancak komşu bir konumda iki birim varsa bu komşu kendi savunmasını tamamen kaybetmeden bir birimi yardıma gönderebilir. Matematiksel olarak önemli olan tarihsel hikâye değil, graf üzerinde yerel koruma koşullarıyla toplam kaynak maliyetinin birlikte optimize edilmesidir.

Komşuluk ve aktif komşuluk

Bir \(u\) tepesinin açık komşuluğu \(N(u)\), \(u\)'ya bitişik tepelerin kümesidir. Kapalı komşuluk ise

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

olarak tanımlanır.

Bir etiketleme \(f\) verildiğinde aktif komşuluk

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

kümesidir. Bu kavram özellikle [k]-Roma baskınlığının tanımında merkezi rol oynar.

[k]-Roma baskınlığı klasik modelden nasıl farklıdır?

\[k]-Roma baskınlığı, her tepeye \(0\) ile \(k+1\) arasında bir etiket verilmesine izin verir ve her tepenin kapalı komşuluğundaki toplam etiketi en az \(k\) artı aktif komşu sayısı kadar yaparak klasik Roma baskınlığını daha genel bir kaynak-tahsis modeline dönüştürür.

Bir [k]-Roma baskınlık fonksiyonu, kısaca [k]-RDF,

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

şeklinde tanımlanır ve her \(u\in V\) için

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

koşulunu sağlamalıdır.

Burada

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

kapalı komşuluktaki etiketlerin toplamıdır. \(|AN(u)|\), \(u\)'nun pozitif etiket taşıyan aktif komşularının sayısıdır. Dolayısıyla gereken minimum toplam yalnız \(k\)'ya değil, aynı zamanda o tepenin çevresinde kaç aktif tepe bulunduğuna da bağlıdır.

Bir graf üzerindeki minimum [k]-Roma baskınlık ağırlığı

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

ile gösterilir.

Kaynağın Şekil 1'i aynı graf üzerinde bir klasik Roma baskınlık etiketlemesi ile bir [k]-Roma etiketlemesini yan yana gösterir. Örnekte klasik değer

\[ \gamma_R(G)=6 \]

iken gösterilen [k]-Roma değeri

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

şeklindedir. Bunlar bütün graflar için genel formüller değil, Şekil 1'deki belirli grafın etiketlemelerini açıklayan değerlerdir.

Güçlü Roma baskınlığı neyi modellemektedir?

Güçlü Roma baskınlığı, tek bir saldırı yerine aynı anda birden fazla korunmasız komşunun savunulabilmesini modellemek için pozitif etiket taşıyan güçlü bir tepenin, 0 etiketli komşularının en az yarısına yetecek savunma ağırlığını taşımasını zorunlu kılan Roma baskınlığı varyantıdır.

Grafın maksimum derecesi \(\Delta\) olsun. Güçlü Roma baskınlık fonksiyonu, kısaca StRDF, tepeleri

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

kümesinden etiketler.

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

0 etiketli tepeler kümesi olmak üzere, her \(v\in B_0\) için bir komşu \(u\) bulunmalı ve

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

koşulu sağlanmalıdır.

Bu formülde \(|N(u)\cap B_0|\), savunucu \(u\)'nun 0 etiketli komşularının sayısıdır. Sağ taraftaki 1 terimi savunucunun kendi korumasını, tavan fonksiyonuyla hesaplanan ikinci terim ise aynı anda savunabileceği korunmasız komşular için gereken ek kapasiteyi temsil eder.

Güçlü Roma baskınlık sayısı

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

ile gösterilir.

Kaynağın Şekil 2'sinde aynı örnek graf için klasik Roma baskınlık ağırlığı 6 iken güçlü Roma baskınlık ağırlığı 8 olarak gösterilir. Bu görsel, çoklu eşzamanlı saldırı koşulunun aynı graf üzerinde daha fazla toplam savunma ağırlığı gerektirebildiğini öğretmek için kullanılmıştır.

Genel alt ve üst sınırlar

Kaynak daha önce bilinen üç temel sınırı kullanır. İlk olarak

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

bağıntısı verilir; burada \(\gamma(G)\) klasik baskınlık sayısıdır.

Mertebesi \(n\) olan bir graf için ayrıca

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

üst sınırı ve

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

alt sınırı kullanılır. Bu sınırlar, ilerleyen kesin-değer ispatlarında bir yapıcı etiketlemenin verdiği üst sınırla zorunlu alt sınırın aynı değerde buluşturulmasına yardımcı olur.

Graf aileleri neden önemlidir?

Genel bir optimizasyon probleminin bütün graflarda çözülmesi zor olabilir; fakat ağaçlar, yollar, çevrimler, iki parçalı graflar veya sınırlı clique-width sınıfları gibi yapısal olarak özel graf ailelerinde daha güçlü algoritmik ve kapalı-form sonuçlar elde edilebilir. Bu çalışmanın temel yaklaşımı da iki yönlüdür: genel problemin hangi yapılarda hesaplama açısından kolay veya zor olduğunu belirlemek ve belirli graf ailelerinde optimum ağırlığı doğrudan formülle hesaplamak.

Çalışmada kullanılan bazı graf aileleri

Çalışmanın Yöntemi ve Bulguları

[k]-Roma baskınlığı hangi graf sınıflarında doğrusal zamanda çözülebiliyor?

[k]-Roma baskınlığı LinEMSOL optimizasyon problemi olarak ifade edilebildiğinden, sınırlı clique-width'e sahip bir graf sınıfında uygun \(r\)-ifadesi girişle birlikte veriliyorsa veya verimli biçimde üretilebiliyorsa minimum [k]-Roma baskınlık fonksiyonu grafın mertebesine göre doğrusal zamanda belirlenebiliyor.

MSOL ve LinEMSOL yaklaşımı

Monadik İkinci Mertebe Mantığı, yani MSOL, yalnız bireysel tepeler üzerinde değil tepe kümeleri üzerinde de niceleme yapılmasına izin verir. Bir grafın bitişiklik ilişkisi

\[ R(u,v) \]

ile temsil edildiğinde birçok kombinatoryal özellik mantıksal formüllerle tanımlanabilir.

LinEMSOL bu yapıyı, monadik kümelerin kardinalitelerinden oluşturulan doğrusal amaç fonksiyonlarıyla genişletir. Makalede bir [k]-Roma etiketlemesi

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

biçiminde tepe kümelerine ayrılır; \(V_j\), etiket değeri \(j\) olan tepelerin kümesidir.

Bu kümelerin \(V\)'nin bir partition'ını oluşturması ve her tepenin [k]-RDF koşulunu sağlaması mantıksal olarak ifade edilir. Optimizasyon amacı

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

şeklindedir.

Bu ifade doğrudan etiket ağırlığını minimize eder. Courcelle yaklaşımı sayesinde problem, uygun ayrıştırma/gösterim mevcut olduğunda sınırlı clique-width sınıflarında doğrusal-zaman algoritmasına taşınabilir.

Kaynağın Corollary 2'sinde sonuç \(f(k)\cdot n\) biçiminde verilir ve örnek sınıflar olarak cographs, distance-hereditary graphs, complete graphs, trees, series-parallel graphs ve outerplanar graphs sayılır.

Güçlü Roma baskınlığı neden NP-tamdır?

Çalışma, güçlü Roma baskınlığı karar probleminin yıldız-konveks iki parçalı graflarda NP-tamlığını, Restricted Exact 3-Cover örneğinden belirli bir yıldız-konveks iki parçalı graf üretip exact cover ile düşük ağırlıklı güçlü Roma etiketlemesinin varlığını birbirine eşdeğer hale getirerek kanıtlıyor.

Karar problemi

Girdi olarak bir

\[ G=(V,E) \]

grafı ve pozitif bir \(k\) tamsayısı veriliyor. Soru şudur:

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

Bir aday etiketlemenin StRDF koşullarını ve ağırlık sınırını polinom zamanda doğrulamak mümkün olduğundan problem NP içindedir.

RX3C'den indirgeme

Restricted Exact 3-Cover probleminde

\[ |X|=3q \]

ve \(C\), üç elemanlı altkümeler ailesidir; her \(x\in X\) tam olarak üç farklı kümede yer alır. Soru, \(X\)'i kesişimsiz olarak tam örten bir \(C^\ast\subseteq C\) ailesinin bulunup bulunmadığıdır.

Kaynak bu örnekten \(\Gamma(I)\) adlı yıldız-konveks iki parçalı grafı oluşturur ve güçlü Roma ağırlık eşiğini

\[ 6q+2 \]

olarak seçer.

İnşada iki parçalı sınıflar

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

şeklindedir. Dolayısıyla

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

\(x_i\) tepesi \(c_j\)'ye ancak ve ancak ilgili eleman ilgili üçlü kümenin içindeyse bağlanır. Ayrıca \(a\), bütün \(c_j\) tepelerine ve \(a_1,a_2\)'ye; her \(c_j\) de kendi \(z_j\)'sine bağlanır.

PDF'nin Şekil 3'ü bu indirgeme grafının iskeletini gösterir. Şeklin bilimsel işlevi, RX3C küme üyeliğinin graf bitişiklik yapısına nasıl kodlandığını görünür kılmaktır.

İspatın ileri yönünde bir exact cover \(C'\) varsa seçilen \(c_j\) tepelerine 3, belirli \(z_i\) tepelerine 1 ve merkez \(a\)'ya \(q+2\) etiketi verilerek toplam ağırlık

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

olan güçlü Roma baskınlık fonksiyonu oluşturulur.

Ters yönde, ağırlığı en fazla \(6q+2\) olan bir optimum StRDF'nin yapısı adım adım kısıtlanarak tam olarak \(q\) adet \(c_j\) tepesinin 3 etiketini taşıması gerektiği ve bunların \(X\)'in exact cover'ını oluşturduğu gösterilir. Böylece RX3C örneğinin “evet” cevabı ile StRDN örneğinin “evet” cevabı eşdeğer hale gelir.

[k]-Roma baskınlığında destek tepeleri

Kaynağın Lemma 1'i yaprak ve destek tepelerinin optimum etiketlemedeki davranışını sınırlar. \(k\geq2\) için zayıf destek tepesi \(v\) ve ona bağlı yaprak \(u\) için

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

Eğer toplam tam \(k\) ise zorunlu olarak

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

Güçlü destek tepesi \(v\), yani en az iki yaprağa komşu bir tepe için ise optimum [k]-Roma etiketlemesinde

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

ve \(v\)'ye bağlı bütün yapraklarda

\[ f(u)=0 \]

olduğu gösterilir. Bu lemma sonraki ağaç ve çift yıldız sonuçlarının temel yapı taşıdır.

[k]-Roma baskınlığında hangi kesin değerler elde edildi?

Çalışma çift yıldızlar için doğrudan formüller, \(n\equiv0\pmod3\) olduğunda yol ve çevrimler için ortak kapalı form ve yolların [k]-Roma reinforcement sayısı için kongruans sınıflarına bağlı sonuçlar elde ediyor.

Çift yıldızlar

\(S_{1,q}\) bir zayıf ve bir güçlü destek tepesine sahip çift yıldız olduğunda

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

sonucu elde edilir.

Her iki merkez de en az iki yaprağa sahipse, yani \(p,q\geq2\) için

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

İkinci formülün arkasındaki yapı basittir: iki merkez de güçlü destek tepesidir ve Lemma 1 gereği her biri \(k+1\) ağırlık taşır; yaprakların optimum etiketi 0'dır.

Yol ve çevrimlerde etiket düzeni

Kaynak, en az dört tepeli bir yol veya çevrimde minimum [k]-Roma fonksiyonunda belirli orta düzey etiketlerin dört ardışık tepede sürekli tekrar edemeyeceğini gösterir. \(k\) çift olduğunda yasak yapı üç ardışık tepeye kadar güçlenir.

Bu tür yerel yapısal kısıtlar, optimum etiketlerin hangi periyodik desenleri oluşturabileceğini anlamaya ve kesin değerlerin türetilmesine yardımcı olur.

Yol ile çevrim karşılaştırması

Bir çevrim, aynı mertebedeki yolun üzerine bir ayrıt eklenerek elde edilebildiğinden, kaynak

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

eşitsizliğini verir.

Belirli bir optimum yol etiketlemesinde \(V_1=\varnothing\) ve \(V_{k+1}=\varnothing\) koşulları sağlanıyorsa daha güçlü sonuç

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

elde edilir.

\(n\equiv0\pmod3\) durumunda kesin değer

\(n\) üçe bölünebiliyorsa hem \(P_n\) hem \(C_n\) için verimli baskın küme her üç tepede bir seçilebilir. Bu durumda

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

olur.

Burada her seçilmiş baskın tepe \(k+1\) ağırlığı taşır ve kapalı komşuluklar grafı çakışmasız biçimde örter.

Yol graflarında reinforcement

Kaynak, [k]-Roma reinforcement sayısını \(r_{[kR]}(G)\) ile gösterir ve temel amaç olarak grafın [k]-Roma baskınlık sayısını azaltmak için kaç yeni ayrıtın yeterli olduğunu inceler.

Kaynak-içi notasyon uyarısı: Definition 1'de \(F\subseteq E(G)\) yazılmıştır; ancak aynı tanım \(G+F\)'yi “\(F\)'deki ayrıtların eklenmesi” olarak açıklamakta ve sonraki ispatta başlangıç yolunda bulunmayan ayrıtlar eklenmektedir. Bu nedenle burada tanımın basılı ifadesi sessizce değiştirilmemiş, sonuçlar Proposition 10'daki açık yapılar üzerinden aktarılmıştır.

\(n\geq4\) için kaynak

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

sonucunu verir.

İspatta kullanılan yol değerleri sırasıyla

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

ve

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

biçimindedir.

Güçlü Roma baskınlığında hangi graf aileleri için kesin formüller bulundu?

Çalışma \(t\)-katlı çarklar, taç grafları, \(C_m\circ K_1\) korona grafları ve her omurga tepesinde en az iki yaprak bulunan belirli tırtıl grafları için güçlü Roma baskınlık sayısını tam olarak belirliyor; daha genel tırtıllar için ise bir üst sınır veriyor.

\(t\)-katlı çarklar

\(W_{m,t}\), bir \(C_m\) çevrimine birbirleriyle komşu olmayan \(t\) merkez tepenin bağlanmasıyla oluşturulur. Proposition 11, güçlü Roma baskınlık sayısının \(m\) ve \(t\)'nin büyüklük ve parite koşullarına bağlı olarak değiştiğini gösterir:

\[ \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 parçalı yapı tesadüf değildir. Çevrim tepelerinin ve merkez tepelerin kaç korunmasız komşuyu aynı anda savunması gerektiği, \(m\) ve \(t\)'nin paritesine göre optimum güçlü tepe yerleşimini değiştirir.

Taç grafı

Taç grafı \(C(n)\), \(K_{n,n}\)'den tam bir eşleme çıkarılarak elde edilir ve toplam \(2n\) tepe içerir. Kaynak şu kesin değeri verir:

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

Tek \(n\)'de genel alt sınır ile yapıcı üst sınır çakışarak \(n+1\)'i verir. Çift \(n\)'de optimum çözümde iki farklı iki parçalı sınıfta güçlü tepe bulunması gerektiği gösterilerek alt sınır \(n+2\)'ye yükseltilir.

PDF'nin Şekil 4'ü \(C(3)\) taç grafında bir minimum güçlü Roma baskınlık fonksiyonunun örneğini gösterir.

Çevrim-korona grafı \(C_m\circ K_1\)

Bir çevrimin her tepesine bir yaprak eklendiğinde \(C_m\circ K_1\) grafı oluşur. Proposition 13 şu tam formülü 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} } \]

Üst sınır, çevrim tepeleri üzerinde dört tepede bir tekrarlanan özel bir \(2,0,0,2\) benzeri etiket yapısı ve yaprak etiketleri kullanılarak inşa edilir. Alt sınırda ise özellikle \(m\equiv0\pmod4\) durumunda bir discharging, yani yük yeniden dağıtma argümanı kullanılır.

Discharging yöntemi ne yapıyor?

İspatta başlangıçta her tepenin yükü kendi etiketi olarak alınır:

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

Daha sonra bazı yapraklardan çevrim tepelerine ve 2 etiketli çevrim tepelerinden komşularına yarım veya bir tam birimlik yükler aktarılır. Bu aktarım toplam yükü değiştirmez:

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

Ancak yeniden dağıtılmış yükler çevrim tepelerinin her biri üzerinde en az \(3/2\)'lik ortalama katkı elde etmeyi mümkün kılar. Sonuç olarak

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

alt sınırı ortaya çıkar ve yapıcı üst sınırla eşleştiğinde kesin değer kanıtlanmış olur.

Özel tırtıl grafları

Omurga, \(v_1,\ldots,v_n\) tepelerinden oluşsun ve her \(v_i\)'ye

\[ x_i\geq2 \]

yaprak bağlı olsun. Bu durumda her omurga tepesi güçlü destek tepesidir. Proposition 14:

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

kesin değerini verir.

Üst sınır için her omurga tepesine

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

etiketi ve bütün yapraklara 0 etiketi verilir. Alt sınır ise her güçlü destek tepesinin ve yapraklarının toplamda en az aynı ağırlığı gerektirmesi üzerinden elde edilir.

PDF'nin Şekil 5'i bu yapıyı görsel olarak gösterir: omurga üzerindeki güçlü destek tepeleri 2 veya 3 gibi pozitif etiketler taşırken bağlı yapraklar 0 etiketlidir. Şeklin rolü kapalı formüldeki her omurga tepesinin yerel katkısını görünür hale getirmektir.

Daha genel tırtıl grafı için üst sınır

Kaynak son olarak omurgada güçlü destek tepelerine ek olarak \(k\) adet zayıf destek tepesi ve destek tepeleri arasında destek olmayan tepelerden oluşan \(q\) adet \(P_{r_j}\) alt yolu bulunmasına izin verir. Bu daha genel durumda kesin değer değil şu üst sınır 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 toplam güçlü destek tepelerini ve onların yapraklarını, \(2k\) terimi zayıf destek tepelerini, son toplam ise destek tepeleri arasındaki ara yolların güçlü Roma baskınlık maliyetini temsil eder.

Kaynak şekillerinin bilimsel işlevleri

Çalışmanın desteklediği sonuçlar

Çalışma, [k]-Roma baskınlığının uygun yapısal graf sınıflarında LinEMSOL ve Courcelle çerçevesiyle doğrusal-zaman çözümüne indirgenebildiğini; güçlü Roma baskınlığının yıldız-konveks iki parçalı graflarda NP-tam olduğunu; ayrıca belirli çift yıldız, yol, çevrim, çark, taç, korona ve tırtıl ailelerinde baskınlık parametrelerinin kapalı biçimde hesaplanabildiğini matematiksel ispatlarla destekler.

Sonuçlar aynı zamanda bir graf optimizasyon probleminin karmaşıklığının yalnız tepe ve ayrıt sayısına değil, grafın yapısal sınıfına da güçlü biçimde bağlı olduğunu gösterir: genel veya belirli iki parçalı sınıflarda karar problemi zor olabilirken sınırlı clique-width/treewidth yapısı ek algoritmik kaldıraç sağlar.

Çalışmanın desteklemediği sonuçlar

Makale gerçek bir askerî, lojistik veya altyapı ağı üzerinde deney yapmaz. “Savunma birimi” dili graf teorisinin tarihsel ve kavramsal yorumudur. Sonuçlar gerçek dünyadaki kaynak tahsisine doğrudan performans garantisi vermez. LinEMSOL sonucu bütün graflarda doğrusal-zaman algoritması olduğu anlamına gelmez; sınırlı clique-width ve uygun gösterim varsayımına bağlıdır. NP-tamlık sonucu da her tekil graf örneğinin pratikte çözülemeyeceği anlamına gelmez; problem sınıfının en kötü durum hesaplama karmaşıklığını ifade eder.

Benzer biçimde, t-katlı çark, taç, korona ve özel tırtıl graf formülleri yalnız belirtilen graf aileleri ve parametre koşulları için geçerlidir; keyfî bir grafın güçlü Roma baskınlık sayısını bu formüllerden çıkarmak mümkün değildir.

Kaynak içindeki iki notasyon sorunu

İlk olarak giriş bölümünde \(P_n\), uzunluğu \(n\) olan ve \(u_0,u_1,\ldots,u_n\) tepelerinden oluşan yol olarak tanımlanırken sonraki sonuçlarda \(P_n\), “mertebesi \(n\)” olan yol anlamında kullanılır. Bu nedenle bu Verianla metninde sonuçlar aktarılırken ilgili teorem veya önermenin kendi “mertebe \(n\)” ifadesi esas alınmıştır; giriş tanımı sessizce yeniden yazılmamıştır.

İkinci olarak [k]-Roma reinforcement tanımında kaynak \(F\subseteq E(G)\) yazar; buna karşın \(G+F\)'yi ayrıt ekleme işlemi olarak tanımlar ve Proposition 10'un konstrüksiyonlarında yolun mevcut ayrıtı olmayan \(v_2v_4\), \(v_6v_8\), \(v_1v_3\) ve \(v_1v_4\) ayrıtlarını ekler. Bu açık kaynak-içi uyumsuzluk nedeniyle Verianla tanımdaki küme ifadesini varsayıma dayalı biçimde değiştirmemiştir.

Kaynak ve Yöntem Notu

Özgün çalışma: Complexity and Exact Values for [k]-Roman and Strong Roman Domination for Specific Graph Families

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

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

Dergi: Mathematics.

Yayınevi: MDPI.

Bibliyografik kayıt: Mathematics 2026, 14(9), 1535.

DOI: 10.3390/math14091535.

Makale süreci: Alınış 19 Şubat 2026; revizyon 6 Nisan 2026; kabul 28 Nisan 2026; yayın 1 Mayıs 2026.

Kaynak türü: Hakemli teorik matematik / ayrık matematik / graf kuramı araştırma makalesi.

Lisans: Creative Commons Attribution (CC BY).

Veri durumu: Yazarlar çalışmada yeni veri oluşturulmadığını veya analiz edilmediğini belirtmektedir. Çalışmanın kanıt materyali graf yapıları, matematiksel tanımlar, teoremler, önermeler ve ispatlardır.

Yazar katkıları: Kavramsallaştırma, metodoloji, doğrulama ve araştırmaya dört yazarın tamamı katkı vermiştir. İlk taslak Martín Cera López ve María Pilar Álvarez-Ruíz; inceleme ve düzenleme Juan Carlos Valenzuela-Tripodoro ve María Antonia Mateos-Camacho tarafından yürütülmüştür. Kaynak bütün yazarların çalışmaya eşit katkıda bulunduğunu ayrıca belirtir.

Finansman: Juan Carlos Valenzuela-Tripodoro; İspanya Bilim, İnovasyon ve Üniversiteler Bakanlığı'nın PID2022-139543OB-C41 projesi ve Avrupa Komisyonu Horizon Europe Marie Skłodowska-Curie Actions Staff Exchanges kapsamındaki 101182819 numaralı COVER projesi tarafından kısmen desteklenmiştir. Martín Cera López; Endülüs Bölgesel Yönetimi Araştırma, Geliştirme ve İnovasyon Planı kapsamındaki FQM-240 projesi ile PPIT-FEDER SOL2024-31708 “Mathematics for Cybersecurity and Smart City Development” projesinden kısmi destek almıştır.

Çıkar çatışması: Yazarlar çıkar çatışması bildirmemiştir.

Kaynak yapısı notu: Makalede ayrı bir “Conclusions” bölümü bulunmaz. Ana bilimsel içerik Proposition 15 ile sona erdikten sonra yazar katkıları, finansman, veri erişilebilirliği ve çıkar çatışması beyanları gelir. Bu nedenle Verianla'daki “çalışmanın desteklediği / desteklemediği” değerlendirmeleri yalnız makaledeki ispatlanmış sonuçlardan türetilmiştir; kaynağa ait olmayan yeni bir sonuç bölümü gibi sunulmamıştır.

Temel yöntemsel sınır: Çalışma deneysel veya ampirik değildir. Algoritmik karmaşıklık sonuçları belirtilen graf sınıfı ve gösterim varsayımlarına; kesin-değer formülleri ise ilgili graf aileleri, parite ve kongruans koşullarına bağlıdır.

Notasyon sınırı: Kaynaktaki \(P_n\) uzunluk/mertebe kullanımı ile reinforcement tanımındaki \(F\subseteq E(G)\) ifadesi, kaynakta göründüğü şekliyle iç tutarsızlık taşımaktadır. Bu Verianla metni bu noktaları gizlememiş ve bilinmeyen düzeltmeyi kaynak sonucu gibi sunmamıştır.

Görsel yeniden çizim uygunluğu: Uygun. Beş kaynak şeklinin tamamı graf-teorik şema olduğundan, düğüm-konumları ve etiketleme mantığı korunarak Verianla için özgün vektörel graf şemaları oluşturulabilir. Amaç piksel kopyalama değil, aynı matematiksel ilişkiyi yeni tasarımla görünür kılmaktır.

Verianla Live / Live Figure: Kısmen uygun. Özellikle Şekil 1–2'de etiketlerin savunma koşulunu nasıl sağladığının sırayla vurgulanması ve Şekil 3'te RX3C'den \(\Gamma(I)\)'ye dönüşümün aşamalı gösterimi source-derived bir Live Figure olarak değerlidir. Kullanıcının grafı veya \(k\) değerini değiştirip yeni optimum sonuç üretmesine izin verilmemelidir; bu, kaynakta yapılmayan yeni hesaplama olur.