Roman domination ni modeli ya uboreshaji wa grafu inayoweka lebo za namba kamili kwenye vilele, zinazoweza kufasiriwa kama rasilimali za ulinzi, ili kuhakikisha vilele vyote vinalindwa chini ya masharti maalumu ya ujirani huku ikipunguza uzito wa jumla wa lebo. Utafiti wa Juan Carlos Valenzuela-Tripodoro, María Antonia Mateos-Camacho, Martín Cera López na María Pilar Álvarez-Ruíz unachunguza aina mbili za hali ya juu za modeli hii, [k]-Roman domination na strong Roman domination, kwa mtazamo wa ugumu wa kihesabu pamoja na thamani sahihi za vigezo katika familia maalumu za grafu.

Kwa upande wa [k]-Roman domination, waandishi wanaeleza tatizo katika mfumo wa Linear Extended Monadic Second-Order Logic (LinEMSOL). Kwa matokeo hayo, ikiwa uwakilishi unaofaa wa grafu unapatikana, tatizo linaweza kutatuliwa kwa muda wa mstari kulingana na order ya grafu katika madarasa yenye clique-width iliyowekewa kikomo. Kwa upande wa strong Roman domination, tatizo la uamuzi linaonyeshwa kuwa NP-complete katika star-convex bipartite graphs kupitia reduction kutoka Restricted Exact 3-Cover.

Mhimili wa pili mkuu wa utafiti ni thamani sahihi. Namba za [k]-Roman au strong Roman domination zinatolewa kwa double stars, baadhi ya paths na cycles, t-fold wheels, crown graphs, corona product ya cycle na kilele kimoja, pamoja na baadhi ya madarasa ya caterpillar graphs. Matokeo si ya majaribio; yanategemea graph labelings, mipaka ya chini na juu ya combinatorics, logical expressibility, complexity reductions na constructive proofs.

Roman domination ni nini?

Roman domination ni modeli ya vertex-labeling optimization inayoweka lebo 0, 1 au 2 kwenye vilele vya grafu na kulazimisha kila kilele chenye lebo 0 kuwa na angalau jirani mmoja mwenye lebo 2; lengo ni kupunguza uzito wa jumla wa lebo zote.

Grafu rahisi, isiyoelekezwa na yenye ukomo

\[ G=(V,E) \]

iwakilishwe hivi. Hapa \(V\) ni seti ya vilele na \(E\) ni seti ya edges. Classical Roman domination function ni

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

kwa namna hii. Ikiwa \(f(v)=0\), basi kwa angalau jirani mmoja \(v\) wa \(u\)

\[ f(u)=2 \]

lazima iwe kweli.

Uzito wa function ni

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

kwa namna hii. Roman domination number ya grafu

\[ \gamma_R(G) \]

ni uzito mdogo zaidi miongoni mwa Roman domination functions zote halali.

Jina “Roman” linatokana na sitiari ya kihistoria ya ulinzi: mahali palipopewa lebo 0 hakuna kitengo cha ulinzi cha moja kwa moja; lakini ikiwa mahali jirani kuna vitengo viwili, jirani huyo anaweza kutuma kitengo kimoja kusaidia bila kupoteza ulinzi wake wote. Kihisabati, cha muhimu si hadithi ya kihistoria, bali kuboresha kwa pamoja masharti ya ulinzi wa ndani kwenye grafu na gharama ya jumla ya rasilimali.

Ujirani na ujirani hai

Open neighborhood ya vertex \(u\), yaani \(N(u)\), ni seti ya vertices zilizo adjacent na \(u\). Closed neighborhood ni

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

kama inavyofafanuliwa.

Labeling \(f\) ikitolewa, active neighborhood ni

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

seti hiyo. Dhana hii ina nafasi kuu hasa katika definition ya [k]-Roman domination.

[k]-Roman domination inatofautianaje na modeli ya kawaida?

\[k]-Roman domination inaruhusu kila vertex kupewa lebo kati ya \(0\) na \(k+1\), na inabadilisha classical Roman domination kuwa modeli pana zaidi ya ugawaji wa rasilimali kwa kutaka jumla ya lebo katika closed neighborhood ya kila vertex iwe angalau \(k\) pamoja na idadi ya active neighbors.

[k]-Roman domination function, kwa kifupi [k]-RDF,

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

inafafanuliwa hivi na lazima kwa kila \(u\in V\) itimize

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

sharti hilo.

Hapa

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

ni jumla ya lebo katika closed neighborhood. \(|AN(u)|\) ni idadi ya active neighbors wa \(u\) wenye lebo chanya. Kwa hiyo jumla ya chini inayohitajika haitegemei \(k\) pekee, bali pia idadi ya active vertices karibu na vertex hiyo.

Uzito wa chini wa [k]-Roman domination kwenye grafu unaandikwa

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

.

Figure 1 ya chanzo inaonyesha labeling ya classical Roman domination na labeling ya [k]-Roman kwenye grafu ileile kwa upande mmoja na mwingine. Katika mfano, thamani ya classical ni

\[ \gamma_R(G)=6 \]

wakati thamani iliyoonyeshwa ya [k]-Roman ni

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

. Hizi si formula za jumla kwa grafu zote, bali ni thamani zinazoeleza labelings za grafu maalumu katika Figure 1.

Strong Roman domination inamodeli nini?

Strong Roman domination ni variant ya Roman domination inayolazimisha strong vertex yenye lebo chanya kuwa na uzito wa ulinzi unaotosha angalau nusu ya majirani zake wenye lebo 0, ili kuwakilisha uwezo wa kulinda majirani wengi wasiolindwa kwa wakati mmoja badala ya shambulio moja tu.

Maximum degree ya grafu iwe \(\Delta\). Strong Roman domination function, kwa kifupi StRDF, inaweka lebo kwenye vertices kutoka seti

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

.

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

ikiwa ni seti ya vertices zenye lebo 0, basi kwa kila \(v\in B_0\) lazima kuwe na jirani \(u\) ambaye

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

.

Katika formula hii \(|N(u)\cap B_0|\) ni idadi ya majirani wenye lebo 0 wa defender \(u\). Term ya 1 upande wa kulia inawakilisha ulinzi wa defender mwenyewe, na term ya pili inayohesabiwa kwa ceiling function inawakilisha uwezo wa ziada unaohitajika kwa majirani wasiolindwa ambao anaweza kuwatetea kwa wakati mmoja.

Strong Roman domination number inaandikwa

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

.

Katika Figure 2 ya chanzo, kwenye grafu ileile ya mfano, classical Roman domination weight inaonyeshwa kuwa 6 huku strong Roman domination weight ikiwa 8. Visual hii imetumika kuonyesha kwamba sharti la mashambulizi mengi ya wakati mmoja linaweza kuhitaji uzito mkubwa zaidi wa jumla wa ulinzi kwenye grafu ileile.

Mipaka ya jumla ya chini na juu

Chanzo kinatumia mipaka mitatu ya msingi iliyojulikana tayari. Kwanza

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

uhusiano huu unatolewa; hapa \(\gamma(G)\) ni classical domination number.

Kwa grafu yenye order \(n\), pia hutumika upper bound

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

na lower bound

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

. Mipaka hii husaidia katika proofs za exact values zinazofuata kwa kuoanisha upper bound inayotokana na constructive labeling na lower bound ya lazima katika thamani moja.

Kwa nini familia za grafu ni muhimu?

Kutatua tatizo la optimization kwa grafu zote kunaweza kuwa vigumu; lakini katika familia maalumu kimuundo kama trees, paths, cycles, bipartite graphs au madarasa yenye bounded clique-width, matokeo yenye nguvu zaidi ya algorithmic na closed-form yanaweza kupatikana. Mkabala mkuu wa utafiti huu pia una pande mbili: kubaini katika miundo ipi tatizo la jumla ni rahisi au gumu kihesabu, na kuhesabu moja kwa moja optimum weight kwa formula katika familia maalumu za grafu.

Baadhi ya familia za grafu zilizotumiwa katika utafiti

Mbinu na Matokeo ya Utafiti

[k]-Roman domination inaweza kutatuliwa kwa muda wa mstari katika madarasa gani ya grafu?

Kwa kuwa [k]-Roman domination inaweza kuelezwa kama LinEMSOL optimization problem, katika darasa la grafu lenye bounded clique-width, ikiwa \(r\)-expression inayofaa imetolewa pamoja na input au inaweza kuzalishwa kwa ufanisi, minimum [k]-Roman domination function inaweza kubainishwa kwa muda wa mstari kulingana na order ya grafu.

Mkabala wa MSOL na LinEMSOL

Monadic Second-Order Logic, yaani MSOL, inaruhusu quantification si juu ya vertices binafsi pekee bali pia juu ya sets za vertices. Ikiwa adjacency relation ya grafu inawakilishwa kwa

\[ R(u,v) \]

, sifa nyingi za combinatorics zinaweza kufafanuliwa kwa logical formulas.

LinEMSOL inapanua muundo huu kwa linear objective functions zilizojengwa kutoka cardinalities za monadic sets. Katika makala, [k]-Roman labeling imegawanywa katika vertex sets kwa namna

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

; \(V_j\) ni seti ya vertices zenye label value \(j\).

Inaelezwa kimantiki kwamba sets hizi zinaunda partition ya \(V\) na kwamba kila vertex inatimiza [k]-RDF condition. Optimization objective ni

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

.

Expression hii inapunguza moja kwa moja label weight. Kwa Courcelle approach, tatizo linaweza kuhamishwa kuwa linear-time algorithm katika bounded clique-width classes ikiwa decomposition/representation inayofaa inapatikana.

Katika Corollary 2 ya chanzo, matokeo yanatolewa katika umbo \(f(k)\cdot n\), na cographs, distance-hereditary graphs, complete graphs, trees, series-parallel graphs na outerplanar graphs yanatajwa kama mfano wa classes.

Kwa nini strong Roman domination ni NP-complete?

Utafiti unathibitisha NP-completeness ya strong Roman domination decision problem katika star-convex bipartite graphs kwa kutengeneza star-convex bipartite graph maalumu kutoka mfano wa Restricted Exact 3-Cover na kufanya uwepo wa exact cover kuwa equivalent na uwepo wa strong Roman labeling yenye weight ndogo.

Decision problem

Kama input hutolewa

\[ G=(V,E) \]

grafu na positive integer \(k\). Swali ni:

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

Kwa kuwa inawezekana kuthibitisha StRDF conditions na weight bound ya candidate labeling kwa polynomial time, tatizo liko ndani ya NP.

Reduction kutoka RX3C

Katika Restricted Exact 3-Cover problem

\[ |X|=3q \]

na \(C\) ni familia ya three-element subsets; kila \(x\in X\) ipo katika sets tatu tofauti haswa. Swali ni kama kuna familia \(X\) inayofunika \(C^\ast\subseteq C\) kikamilifu bila overlap.

Chanzo kinatengeneza star-convex bipartite graph inayoitwa \(\Gamma(I)\) kutoka mfano huu na kuchagua strong Roman weight threshold kuwa

\[ 6q+2 \]

.

Katika construction, bipartite classes ni

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

. Kwa hiyo

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

Vertex \(x_i\) inaunganishwa na \(c_j\) ikiwa na ikiwa tu element inayohusika ipo ndani ya triple set inayohusika. Zaidi ya hayo, \(a\) inaunganishwa na vertices zote za \(c_j\) na \(a_1,a_2\); kila \(c_j\) pia inaunganishwa na \(z_j\) yake.

Figure 3 ya PDF inaonyesha skeleton ya reduction graph hii. Jukumu la kisayansi la figure ni kuonyesha namna set membership ya RX3C inavyokodishwa kwenye adjacency structure ya grafu.

Katika forward direction ya proof, ikiwa kuna exact cover \(C'\), labels 3 huwekwa kwenye selected \(c_j\) vertices, label 1 kwenye baadhi ya \(z_i\) vertices, na label \(a\) kwenye center \(q+2\), na strong Roman domination function yenye total weight

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

inatengenezwa.

Katika reverse direction, muundo wa optimum StRDF wenye weight isiyozidi \(6q+2\) unabanwa hatua kwa hatua na kuonyeshwa kwamba exactly \(q\) vertices za \(c_j\) lazima zibebe label 3 na kwamba hizo zinaunda exact cover ya \(X\). Hivyo jibu la “ndiyo” la RX3C instance linakuwa equivalent na jibu la “ndiyo” la StRDN instance.

Support vertices katika [k]-Roman domination

Lemma 1 ya chanzo inaweka mipaka kwa tabia ya leaves na support vertices katika optimum labeling. Kwa \(k\geq2\), kwa weak support vertex \(v\) na leaf \(u\) iliyounganishwa nayo,

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

Ikiwa jumla ni \(k\) haswa, basi lazima

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

Kwa strong support vertex \(v\), yaani vertex inayokuwa adjacent na angalau leaves mbili, katika optimum [k]-Roman labeling inaonyeshwa kuwa

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

na kwa leaves zote zilizounganishwa na \(v\)

\[ f(u)=0 \]

. Lemma hii ndiyo msingi wa matokeo ya baadaye ya trees na double stars.

Ni exact values zipi zilipatikana katika [k]-Roman domination?

Utafiti unatoa formulas za moja kwa moja kwa double stars, closed form ya pamoja kwa paths na cycles wakati \(n\equiv0\pmod3\), na matokeo yanayotegemea congruence classes kwa [k]-Roman reinforcement number ya paths.

Double stars

Wakati \(S_{1,q}\) ni double star yenye weak support vertex moja na strong support vertex moja,

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

inapatikana.

Ikiwa centers zote mbili zina angalau leaves mbili, yaani kwa \(p,q\geq2\)

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

Muundo nyuma ya formula ya pili ni rahisi: centers zote mbili ni strong support vertices na kwa Lemma 1 kila moja hubeba weight \(k+1\); optimum label ya leaves ni 0.

Label pattern katika paths na cycles

Chanzo kinaonyesha kwamba katika minimum [k]-Roman function kwenye path au cycle yenye angalau vertices nne, baadhi ya labels za kiwango cha kati haziwezi kurudiwa mfululizo katika vertices nne zinazofuatana. Wakati \(k\) ni even, prohibited structure inakuwa kali zaidi hadi vertices tatu zinazofuatana.

Vizuizi hivi vya local structure vinasaidia kuelewa periodic patterns ambazo optimum labels zinaweza kuunda na kusaidia katika kutoa exact values.

Ulinganisho wa path na cycle

Kwa kuwa cycle inaweza kupatikana kwa kuongeza edge moja kwenye path yenye order ileile, chanzo kinatoa inequality

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

.

Ikiwa katika optimum path labeling maalumu masharti \(V_1=\varnothing\) na \(V_{k+1}=\varnothing\) yanatimizwa, matokeo yenye nguvu zaidi

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

yanapatikana.

Exact value wakati \(n\equiv0\pmod3\)

Ikiwa \(n\) inagawanyika kwa tatu, efficient dominating set inaweza kuchaguliwa kila baada ya vertices tatu kwa \(P_n\) na \(C_n\). Katika hali hii

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

.

Hapa kila selected dominating vertex hubeba weight \(k+1\), na closed neighborhoods zinafunika grafu bila overlap.

Reinforcement katika path graphs

Chanzo kinaandika [k]-Roman reinforcement number kama \(r_{[kR]}(G)\) na kinachunguza kama lengo kuu ni edges mpya ngapi zinatosha kupunguza [k]-Roman domination number ya grafu.

Onyo la notation ndani ya chanzo: Katika Definition 1 imeandikwa \(F\subseteq E(G)\); hata hivyo definition hiyo hiyo inaeleza \(G+F\) kama “kuongeza edges zilizo katika \(F\)” na katika proof inayofuata edges zisizokuwepo katika path ya mwanzo zinaongezwa. Kwa hiyo hapa expression iliyochapishwa ya definition haijabadilishwa kimya kimya, na matokeo yamewasilishwa kupitia constructions zilizo wazi katika Proposition 10.

Kwa \(n\geq4\), chanzo kinatoa

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

.

Path values zinazotumika katika proof ni kwa mtiririko

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

na

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

.

Ni familia zipi za grafu zilipata formulas sahihi za strong Roman domination?

Utafiti unabainisha kabisa strong Roman domination number kwa \(t\)-fold wheels, crown graphs, \(C_m\circ K_1\) corona graphs na baadhi ya caterpillar graphs ambamo kila backbone vertex ina angalau leaves mbili; kwa caterpillars za jumla zaidi, unatoa upper bound.

\(t\)-fold wheels

\(W_{m,t}\) huundwa kwa kuunganisha \(C_m\) center vertices zisizo adjacent kwa kila mmoja kwenye cycle \(t\). Proposition 11 inaonyesha kwamba strong Roman domination number hubadilika kulingana na ukubwa na parity conditions za \(m\) na \(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} \]

Muundo huu wa piecewise si wa bahati. Idadi ya majirani wasiolindwa ambao cycle vertices na center vertices lazima walinde kwa wakati mmoja hubadilisha optimum placement ya strong vertices kulingana na parity ya \(m\) na \(t\).

Crown graph

Crown graph \(C(n)\) hupatikana kwa kuondoa perfect matching kutoka \(K_{n,n}\) na ina jumla ya \(2n\) vertices. Chanzo kinatoa exact value ifuatayo:

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

Kwa odd \(n\), general lower bound na constructive upper bound zinafanana na kutoa \(n+1\). Kwa even \(n\), inaonyeshwa kwamba optimum solution lazima iwe na strong vertex katika bipartite classes mbili tofauti, hivyo lower bound inapandishwa hadi \(n+2\).

Figure 4 ya PDF inaonyesha mfano wa minimum strong Roman domination function katika crown graph \(C(3)\).

Cycle-corona graph \(C_m\circ K_1\)

Leaf moja inapoongezwa kwenye kila vertex ya cycle, grafu \(C_m\circ K_1\) huundwa. Proposition 13 inatoa exact formula ifuatayo:

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

Upper bound inajengwa kwa kutumia special label pattern inayofanana na \(2,0,0,2\) inayojirudia kila vertices nne kwenye cycle pamoja na labels za leaves. Katika lower bound, hasa katika hali \(m\equiv0\pmod4\), discharging, yaani hoja ya redistribution ya charge, inatumika.

Discharging method inafanya nini?

Katika proof, mwanzoni charge ya kila vertex huchukuliwa kuwa label yake yenyewe:

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

Kisha half-unit au one-unit charges huhamishwa kutoka baadhi ya leaves kwenda cycle vertices na kutoka cycle vertices zenye label 2 kwenda kwa neighbors wao. Uhamisho huu haubadilishi total charge:

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

Lakini redistributed charges zinawezesha kupata average contribution ya angalau \(3/2\) kwa kila cycle vertex. Matokeo yake

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

lower bound inatokea, na inapolingana na constructive upper bound exact value inathibitishwa.

Special caterpillar graphs

Backbone iwe na vertices \(v_1,\ldots,v_n\), na kila \(v_i\) iwe imeunganishwa na

\[ x_i\geq2 \]

leaves. Katika hali hii kila backbone vertex ni strong support vertex. Proposition 14 inatoa

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

exact value.

Kwa upper bound, kila backbone vertex inapewa

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

label na leaves zote zinapewa label 0. Lower bound hupatikana kwa ukweli kwamba kila strong support vertex na leaves zake kwa pamoja zinahitaji angalau weight hiyo hiyo.

Figure 5 ya PDF inaonyesha muundo huu kwa visual: strong support vertices kwenye backbone hubeba positive labels kama 2 au 3, huku leaves zilizounganishwa zikiwa na label 0. Jukumu la figure ni kuonyesha local contribution ya kila backbone vertex katika closed-form formula.

Upper bound kwa caterpillar graph ya jumla zaidi

Mwishowe chanzo kinaruhusu backbone kuwa na \(k\) weak support vertices pamoja na strong support vertices, na \(q\) subpaths \(P_{r_j}\) zenye vertices zisizo support kati ya support vertices. Katika hali hii ya jumla zaidi, si exact value bali upper bound ifuatayo hutolewa:

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

Jumla ya kwanza inawakilisha strong support vertices na leaves zao, term \(2k\) weak support vertices, na jumla ya mwisho gharama ya strong Roman domination ya paths za kati ya support vertices.

Majukumu ya kisayansi ya figures za chanzo

Hitimisho zinazoungwa mkono na utafiti

Utafiti unaunga mkono kwa mathematical proofs kwamba [k]-Roman domination inaweza kupunguzwa kuwa linear-time solution kupitia LinEMSOL na Courcelle framework katika structural graph classes zinazofaa; strong Roman domination ni NP-complete katika star-convex bipartite graphs; na domination parameters zinaweza kuhesabiwa kwa closed form katika baadhi ya double-star, path, cycle, wheel, crown, corona na caterpillar families.

Matokeo pia yanaonyesha kwamba complexity ya graph optimization problem haitegemei tu idadi ya vertices na edges bali pia structural class ya grafu: decision problem inaweza kuwa ngumu katika general au baadhi ya bipartite classes, huku bounded clique-width/treewidth structure ikitoa algorithmic leverage ya ziada.

Hitimisho zisizoungwa mkono na utafiti

Makala haifanyi experiment kwenye military, logistics au infrastructure network halisi. Lugha ya “defense unit” ni tafsiri ya kihistoria na kidhana ya graph theory. Matokeo hayatoi direct performance guarantee kwa real-world resource allocation. Matokeo ya LinEMSOL hayamaanishi kuwa kuna linear-time algorithm kwa grafu zote; yanategemea bounded clique-width na assumption ya representation inayofaa. NP-completeness result pia haimaanishi kwamba kila graph instance binafsi haiwezi kutatuliwa kivitendo; inaeleza worst-case computational complexity ya problem class.

Vivyo hivyo, formulas za t-fold wheel, crown, corona na special caterpillar graphs ni halali tu kwa graph families na parameter conditions zilizotajwa; haiwezekani kutoa strong Roman domination number ya arbitrary graph kutoka formulas hizi.

Masuala mawili ya notation ndani ya chanzo

Kwanza, katika introduction \(P_n\) inafafanuliwa kama path yenye length \(n\) na vertices \(u_0,u_1,\ldots,u_n\), huku katika matokeo yanayofuata \(P_n\) ikitumika kwa maana ya path yenye “order \(n\)”. Kwa hiyo katika maandishi haya ya Verianla, wakati wa kuwasilisha matokeo, expression ya “order \(n\)” ya theorem au proposition husika imechukuliwa kuwa msingi; definition ya introduction haijaandikwa upya kimya kimya.

Pili, katika definition ya [k]-Roman reinforcement, chanzo kinaandika \(F\subseteq E(G)\); hata hivyo kinafafanua \(G+F\) kama edge-addition operation na katika constructions za Proposition 10 kinaongeza edges \(v_2v_4\), \(v_6v_8\), \(v_1v_3\) na \(v_1v_4\), ambazo si edges zilizopo za path. Kwa sababu ya inconsistency hii ya wazi ndani ya chanzo, Verianla haijabadilisha set expression katika definition kwa kutegemea assumption.

Maelezo ya Chanzo na Mbinu

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

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

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

Jarida: Mathematics.

Mchapishaji: MDPI.

Rekodi ya bibliografia: Mathematics 2026, 14(9), 1535.

DOI: 10.3390/math14091535.

Mchakato wa makala: Ilipokelewa 19 Februari 2026; marekebisho 6 Aprili 2026; ilikubaliwa 28 Aprili 2026; ilichapishwa 1 Mei 2026.

Aina ya chanzo: Makala ya utafiti wa theoretical mathematics / discrete mathematics / graph theory iliyopitiwa na wenzao.

Leseni: Creative Commons Attribution (CC BY).

Hali ya data: Waandishi wanaeleza kuwa hakuna data mpya iliyoundwa au kuchanganuliwa katika utafiti. Nyenzo za uthibitisho za utafiti ni graph structures, mathematical definitions, theorems, propositions na proofs.

Michango ya waandishi: Waandishi wote wanne walichangia katika conceptualization, methodology, validation na investigation. Rasimu ya kwanza ilifanywa na Martín Cera López na María Pilar Álvarez-Ruíz; review na editing zilifanywa na Juan Carlos Valenzuela-Tripodoro na María Antonia Mateos-Camacho. Chanzo pia kinaeleza wazi kwamba waandishi wote walichangia kwa kiwango sawa katika utafiti.

Ufadhili: Juan Carlos Valenzuela-Tripodoro; aliungwa mkono kwa sehemu na mradi PID2022-139543OB-C41 wa Ministry of Science, Innovation and Universities ya Spain na mradi COVER nambari 101182819 chini ya European Commission Horizon Europe Marie Skłodowska-Curie Actions Staff Exchanges. Martín Cera López; alipata msaada wa sehemu kutoka mradi FQM-240 chini ya Research, Development and Innovation Plan ya Andalusian Regional Government na mradi PPIT-FEDER SOL2024-31708 “Mathematics for Cybersecurity and Smart City Development”.

Mgongano wa maslahi: Waandishi hawakuripoti mgongano wa maslahi.

Dokezo la muundo wa chanzo: Makala haina sehemu tofauti ya “Conclusions”. Baada ya maudhui makuu ya kisayansi kumalizika na Proposition 15, zinafuata author contributions, funding, data availability na conflict-of-interest statements. Kwa hiyo tathmini za “utafiti unaunga mkono / hauungi mkono” katika Verianla zimetolewa tu kutokana na matokeo yaliyothibitishwa katika makala; hazijawasilishwa kama sehemu mpya ya hitimisho isiyokuwepo katika chanzo.

Kikomo kikuu cha kimetodolojia: Utafiti si wa experimental wala empirical. Algorithmic complexity results zinategemea graph class na representation assumptions zilizotajwa; exact-value formulas zinategemea graph families husika pamoja na parity na congruence conditions.

Kikomo cha notation: Matumizi ya \(P_n\) kuhusu length/order na expression \(F\subseteq E(G)\) katika reinforcement definition yana inconsistency ya ndani kama yanavyoonekana katika chanzo. Maandishi haya ya Verianla hayajaficha pointi hizi wala kuwasilisha correction isiyojulikana kama matokeo ya chanzo.

Ufaafu wa kuchora upya visual: Unafaa. Kwa kuwa figures zote tano za chanzo ni graph-theoretic diagrams, Verianla inaweza kutengeneza original vector graph diagrams kwa kuhifadhi node positions na labeling logic. Lengo si pixel-copying, bali kuonyesha uhusiano uleule wa kihisabati kwa design mpya.

Verianla Live / Live Figure: Inafaa kwa sehemu. Hasa katika Figures 1–2, kuonyesha hatua kwa hatua jinsi labels zinavyotimiza defense condition, na katika Figure 3, kuonyesha transformation kutoka RX3C kwenda \(\Gamma(I)\) hatua kwa hatua, kuna thamani kama source-derived Live Figure. Mtumiaji hapaswi kuruhusiwa kubadilisha grafu au thamani ya \(k\) na kutengeneza optimum result mpya; hiyo ingekuwa computation mpya ambayo haikufanywa katika chanzo.