RIMSKO DOMINANTNO ŠTEVILO
POLONA PAVLICJANEZ ŽEROVNIK2'3
1 Fakulteta za naravoslovje in matematiko, Univerza v Mariboru 2Fakulteta za strojništvo, Univerza v Ljubljani 3InStitut za matematiko, fiziko in mehaniko
Math. Subj. Class. (2010): 05C69
Na podlagi motivacije iz vsakdanjega življenja predstavimo koncept dominacije ter rimske dominacije. NatanCneje se posvetimo slednji. Predstavimo nekaj osnovnih lastnosti koncepta ter jih uporabimo za dolocitev vrednosti rimskih dominantnih stevil nekaterih posebnih družin grafov.
THE ROMAN DOMINATION NUMBER
We present a concept of the domination and the Roman domination based on motivation from everyday life. We focus our attention to the Roman domination and present some basic properties of this graph invariant. Using these properties we determine the exact values of the Roman domination number of some special graph classes.
Uvod
Predstavljajmo si, da želimo po državi razporediti centre za reševanje tako, da bo teh Cim manj in da bodo resevalci prispeli na pomoC v vsako obCino v dogovorjeno kratkem Casu. Probleme te vrste uCinkovito opisemo v jeziku teorije grafov takole: Vsako lokaCijo predstavimo s toCko, imenovano vozlišče, med dvema lokaCijama pa narisemo Crto (pravimo ji povezava), Ce obstaja (hitra) pot med tema lokaCijama. Tako mnoziCo vozlisC skupaj s povezavami imenujemo graf in jo oznaCimo z G = (V,E), kjer V pomeni mnoziCo vozlisC, E pa mnoziCo povezav, tj. urejenih parov vozlisC. Ce med dvema vozlisCema obstaja povezava, pravimo, da sta sosednji. MnoziCo vseh sosedov vozlisCa u grafa G po navadi oznaCimo z N(u). Naj bo se N [u] = N (u) U {u}. Število sosedov vozlisCa u imenujemo stopnja vozlišča u. NajveCjo med vsemi stopnjami vozlisC vCasih oznaCimo z A(G).
Problem razporeditev resevalnih enot lahko sedaj opisemo takole: obCine predstavimo z grafom, nato pa vsako vozlisCe oznaCimo bodisi z 0 bodisi z 1. Pri tem 0 pomeni, da na lokaCiji ni resevalne enote, 1 pa, daje. Ce te oznake grafa izberemo tako, da je vsaka 0 sosednja z neko 1, potem dobimo zgoraj opisano situaCijo. Pravimo, da smo tedaj graf dominirali, najmanjsemu moznemu stevilu eniC, ki jih potrebujemo, da bo graf dominiran, pa pravimo dominantno število grafa,, 7(G). MnoziCi vozlisC, oznaCenih z 1 v dominaCiji grafa, pravimo tudi dominantna mnoZica. Dominantni mnoziCi, ki ima 7(G) elementov, vCasih reCemo tudi 7-mnoZica.
Poglejmo sedaj nekaj primerov dominantnih števil preprostih grafov, ki
jih najdemo na sliki 1. Prvi primer predstavlja graf, ki ima vse možne
povezave na danih vozlisčih. Imenujemo ga poln graf na sestih vozliscih.
Poln graf na n vozliscih označimo s Kn. Očitno je y) = 1. VozlisCe
dominantne mnozice je obarvano temneje. Na tem mestu definirajmo se
komplement grafa G, ki ga označimo z G. To je graf, katerega mnozica
vozli sc je enaka mnozici vozli sc grafa G, povezave v komplementu pa so
med tistimi vozlisci, kjer v osnovnem grafu povezav ni bilo. Komplement
polnega grafa je graf brez povezav. Ocitno je 7(Kn) = n. Drugi graf
s slike 1 imenujemo cikel na n vozliscih, Cn. Razmislite, da je v splosnem n
l(Cn) =
Pn. Tak gra:
n
Zadnji graf na sliki 1
imenujemo mreza ter jo oznacimo z Gk,n. V nasem primeru je k = 4 in n = 3. Za te grafe je bila dolocitev dominantnega stevila dolga leta neznanka - obstajala je domneva, ki pa ni bila dokazana vse do leta 2011 [3].
. Podobno velja tudi za grafe, imenovane poti na n vozli scih, ima podobno kot cikel n vozlisc, med njimi pa izpustimo eno
n
izmed povezav cikla. Tudi zanje je 7(Pn) = —
-o
-o
0-r	p-< S ^	»-0
0-C	J L 3-(	»-0
Slika 1. Dominantne množice nekaterih grafov.
Rimska dominacija
S taksnim opisom razporeditev re sevalnih enot v mestu se nam lahko zgodi sledeca situacija: re s evalna enota iz mesta, oznacenega z 1, mora posredovati pri nekem sosedu, ki nima svoje re s evalne enote (je oznaceno z 0). Hkrati pa se v tem mestu, ki je poslalo re sevalno ekipo k sosedom, zgodi nesreca.
V taki obliki dominacije torej nimamo nikakrsne rezerve, ki pa je v realnih situacijah se kako pomembna. Enega takih zanimivih problemov je ze v casu svojega vladanja rimskemu imperiju v 4. stoletju postavil cesar Konstantin [6, 7, 8]. Ko je prevzel vladanje rimskemu imperiju, se je ta raztezal od severne Afrike, prek Male Azije do polovice Britanije ter cez celotno Iberijo na zahodu (slika 2). Predhodniki so cesarju v dolga leta tra-jajocih vojnah osvojili ogromno ozemlja, a sosednji narodi so vse mocneje vpadali na zavzeta obmocja in vojska rimskega imperija se je ob posredovanjih prepolovila. Konstantin je tako postavil vprasanje, kako z legijami, ki so mu ostale, zastraziti province tako, da bodo bodisi zastrazene z manj so enoto vojske, bodisi bo v provinco lahko prisel na pomoc del vojske iz so-
Slika 2. Rimski imperij v 2. stoletju [9].
sednje province, ki pa bo zastražena z večjo enoto vojske in tako tudi po posredovanju pri sosedih ne bo ostala nezastraZena.
Opazimo, da je tudi to neke vrste dominacija, vendar tukaj dominiramo graf, ki predstavlja na primer ozemlje rimskega imperija, z dvema različnima vrstama vozlisc - takimi, ki dominirajo le sebe, ter takimi, ki dominirajo sebe ter vsa sosednja vozlisCa. V jeziku teorije grafov bomo sedaj vozlisCa grafa označili z elementi mnozice {0,1,2} tako, da bo vsako vozlisCe, označeno z 0, sosednje z vsaj enim, ki je oznaceno z 2. Vozlisca, oznacena z 1, rabijo le za to, da dominirajo sama sebe in nimajo vpliva na sosede. Tak tip dominacije po zgodbi, ki smo jo navedli zgoraj, imenujemo rimska dominacija. Najmanjsa izmed vsot takih oznak vozlisc je rimsko dominantno ■število grafa. Poglejmo si se formalno definicijo [2]:
Definicija 1. Rimska dominantna funkcija grafa G = (V, E) je taka preslikava f : V —^ {0,1, 2}, pri kateri je vsako vozlisce u s f (u) = 0, sosednje z nekim vozliscem v s f (v) = 2. Vrednost rimske dominantne funkcije je ste-vilo w(f) ^ X]	f (v). Najmanjsi vrednosti rimske dominantne funkcije
grafa G pravimo rimsko dominantno število grafa G in ga oznacimo z jr(G).
Rimsko dominantno funkcijo (kratko RDF), ki realizira w(f) = yr(G), imenujemo tudi YR-funkcija. Glede na neko rimsko dominantno funkcijo
f lahko množico vozlišč grafa G zapišemo kot urejeno particijo (Vq, Vi, V2) množice V, kjer je Vi = {v G V | f (v) = i} za i G {0,1,2}. Pišemo tudi f = (Vc),Vi,V2). Vpeljimo še oznako Ui = IV^I za število vozlišč v Vi za i = 0,1,2. V tem jeziku je vrednošt rimške dominantne funkcije f = (Vq, Vi, V2) enaka w(f) = Ui + 2u2.
Razmišlite, da lahko na tak nacin š pomocjo enega vozlišca z oznako 2 ucinkovito odbijemo le en napad na njegovega šošeda, ki ima oznako 0. Primer, ko lahko vozlišce pošreduje pri vec hkratnih napadih na šošednje vozlišce, natancneje pojašnjuje definicija k-rimškega dominantnega števila [4], ki pa je tukaj ne bomo podrobneje opišovali.
Dodajmo še, da je dovolj preucevati povezane grafe (take, pri katerih za poljubni dve vozlišci obštaja pot med njima). Namrec, (rimško) dominantno število grafa, ki ni povezan, je všota (rimških) dominantnih števil njegovih povezanih komponent (delov). Zato, ce ne bo pošebej pišalo, imejmo v mišlih povezane grafe.
Lastnosti rimskih dominantnih funkcij
Zacnimo z nekaterimi preproštimi pošledicami definicije rimškega dominantnega števila, ki bodo korištne tako pri dokazovanju izrekov kot tudi za boljšo predštavo o konceptu.
Trditev 2 ([1, 2]). Naj bo G = (V, E) graf na vsaj treh vozliščih in f = (Vc), V1, V2) neka jR-funkcija grafa G. Potem velja:
1.	V1 U V2 je dominantna mnošica grafa G;
2.	V2 je Y-mnošica grafa, induciranega1 na Vq U V2;
3.	neko vozlišče iz Vi je sosednje še največ z enim vozliščem iz Vi;
4.	med vozlišči mnošic Vi in V2 ni povezav;
5.	YR (G) < IV (G) I- A(G) + 1.
Dokaz. Tocki 1 in 2 šledita direktno iz definicije rimškega dominantnega števila. Tocko 3 dokazemo takole: Naj bo f = (Vcc, Vi, V2) 7R-funkcija grafa G. Ce bi bilo neko vozlišce u G Vi šošednje z dvema razlicnima vozlišcema v,w G V1, lahko tvorimo novo rimško dominantno funkcijo g takole: naj bo g(u) = 2, g(v) = g(w) = 0 ter g(x) = f (x) za vša druga vozlišca grafa G. Opazimo, da ima rimška dominantna funkcija g vrednošt za 1 manjšo od najmanjše mozne, kar je protišlovje.
^Graf, induciran na množici X C V (G), je graf, katerega množica vozlišč je množica X, povezave med vozlišci iz X pa so vse, ki so bile povezave med temi vozlišci tudi že v grafu G.
Poglejmo se točko 4. Naj bo f = (Vo, Vi, V2) taka 7R-funkcija grafa G, da je uv povezava grafa G in je f (u) = 1 ter f (v) = 2. Potem je tudi f' = (Vo U {u}, Vl \ {u}, V2) yr-funkcija grafa G z za 1 manjšo vrednostjo, kar pa je protislovje (f je bila 7R-funkcija, torej RDF najmanjše vrednosti, mi pa smo nasli se manjso).
Nazadnje se lotimo se točke 5. Naj bo vozlisCe u vozlisCe največje stopnje v G. Potem je f = (N (u), V (G) \ N [u] , {u}) RDF grafa G vrednosti w(f) = (|V(G)| - (A(G) + 1)) + 2 = |V(G)| - A(G) + 1.	.
Ker očitno obstaja povezava med dominantnim stevilom ter rimskim dominantnim stevilom, bomo v nadaljevanju natančneje preučili, kaksen je odnos med tema grafovskima invariantama.
Trditev 3. Naj bo G graf. Potem velja:
1. 7(G) < yr(g) < 27(G);
2. 7R(G) = 7(G) natanko tedaj, ko je G = Kn.
Dokaz. Naj bo D neka 7-mnoziča grafa G. Potem je (V (G) \ D, 0, D) rimska dominantna funkčija grafa G vrednosti 27(G). Zato je 7R(G) < 27(G). Za poljubno 7R-funkčijo f = (Vo, Vl,V2) grafa G pa je mnoziča Vl U V2 očitno tudi dominantna mnoziča grafa (ne nujno najmanj s a), zato je 7(G) < nl + n2 < nl + 2n2 = 7R(G), in tako je dokazana prva trditev.
Za grafe brez povezav je očitno 7R(G) = 7(G). Vzemimo nazadnje se tak graf G, da je 7R(G) = 7(G), in naj bo f = (Vo, Vl, V2) neka njegova 7R-funkčija. Ker je Vl U V2 dominantna mnoziča, je, podobno kot zgoraj, 7(G) < nl + n2 < nl + 2n2 = 7R(G), vendar morajo po predpostavki, če pogledamo začetek in koneč neenakosti, povsod v resniči nastopati enačaji. Zato je n2 = IV2I =0. Po definičiji RDF je zato tudi Vo = 0. Torej je 7R(G) = nl = |V(G)| = n in zato tudi 7(G) = n, iz česar pa sledi, da je G nujno graf .	■
Dodajmo se, da graf G, ki zadosča enakosti 7R(G) = 27(G), imenujemo rimski graf. Ena moznih preprostih karakterizačij rimskih grafov je naslednja:
Trditev 4. Graf G je rimski graf natanko tedaj, ko obstaja taka YR-funkcija grafa G, da je Vl = 0.
Dokaz. Naj bo G graf in rečimo, da obstaja taka 7R-funkčija f = (Vo, Vl, V2) grafa G, da je Vl = 0. Potem je vrednost te 7R-funkčije w(f) = nl + 2n2 = 0 + 2n2, in ker je mnoziča V2 tudi dominantna mnoziča, je w(f) = 2n2 > 27(G). Po trditvi 3 je w(f) = 7r(G) < 27(G), zato je w(f) = 27(G). Torej je G rimski graf.
Za dokaz v drugo smer vzemimo rimski graf G. To je tak graf, da je 7R(G) = 27(G). Ker je Vi U V2 dominantna mnoZica grafa G ter je Vi n V2 = 0, je 7(G) < | Vi U V2I = ni + n2. Ker pa je G rimski graf, je
27(G) = 2ni + 2n2 = 7r(G) = ni + 2n2, iz Cesar sledi, da je nl = 0 oziroma Vl = 0.	■
Na primerih s slike 1 so rimski grafi polni grafi za n > 1 ter cikli Csk in C3k+2. Tretji graf s slike 1, mreza G4,3, je primer grafa, ki ni rimski. Razmislite, da je Yr(G4,3) = 7.
Glede na trditev 3 bi bilo zanimivo pogledati se, koliksna je lahko dejanska razlika med in 27. Iz preprostega primera grafa, imenovanega subdividirana zvezda, S i,8 na sliki 3, lahko vidimo, daje razlika med Yr(G) in 27(G) lahko poljubno velika. Na desni sliki, ki prikazuje 7R-funkcijo, je Crno vozlisCe iz V2 v 7R-funkciji, siva vozlisCa pa so vozlisCa iz Vl v 7R-funkciji. V splosnem za subdividirano zvezdo velja, daje rimsko dominantno stevilo yr (S= 2 + n, medtem ko je dvakratnik dominantnega stevila 27 (Si,„) = 2n.
Slika 3. 7-množica in 7R-funkcija subdividirane zvezde Si,8-
DoloCiti rimsko dominantno stevilo poljubnega grafa je zelo tezek problem. V matematiki take tezke probleme (veCina res zanimivih je takih) imenujemo NP-polni problemi. Pojasnimo, kaj to pomeni.
Recimo, da imamo neki odloCitveni problem. To je tak, na katerega lahko odgovorimo z da ali ne. Ce zanj obstaja resitev, ki jo lahko poi-sCemo dovolj hitro (v jeziku algoritmov v polinomskem Casu), pravimo, da ta problem pripada razredu P. Ce pa za problem znamo za mozno resitev v polinomskem Casu preveriti, ali je prava, pravimo, da problem pripada razredu NP. Gotovo je P C NP, ne ve pa se, ali je morda P = NP. VeCina raziskovalcev deluje, kot da to ni res. Problem, ali je P = NP, je eden od sedmih problemov tisoCletja, ki jih je leta 2000 objavil ameriski
Clay MathematiCs Institute. Za resitev vsakega od njih je razpisal nagrado milijon ameriskih dolarjev. Do danes je bil resen le eden (PoinCarejeva domneva). Torej ob predpostavki, da je P = NP, to, da je neki problem NP-poln, nekoliko poenostavljeno reCeno pomeni, da ne obstaja dovolj hiter algoritem (polinomski), ki bi poiskal resitev zastavljenega problema, le za mozno resitev lahko dovolj hitro preverimo, ali je prava. V nasem primeru je tak problem doloCitev rimskega dominantnega stevila poljubnega grafa [1]. Zato so se razliCni raziskovalCi omejevali na iskanje rimskih dominantnih stevil manjsih druzin grafov. O nekaterih rezultatih smo govorili ze pri rimskih grafih (za polne grafe in Cikle).
Grafi z majhnimi rimskimi dominantnimi števili
Za koneC se karakterizirajmo grafe, ki imajo rimsko dominantno stevilo 2 ali 3. Take grafe bomo opisali v jeziku maksimalne stopnje vozlisC grafa. Rimsko dominantno stevilo 2 imajo natanko tisti grafi, ki premorejo vozli-sCe stopnje |V(G)| — 1, rimsko dominantno stevilo 3 pa grafi, ki premorejo vozli sCe stopnje |V(G)| — 2, ne pa vozli sCa stopnje |V(G)| — 1.
Trditev 5 ([5]). Za povezan graf G na vsaj dveh vozliščih so naslednje trditve ekvivalentne:
1.	YR(G) = 2;
2.	7(G) = 1;
3.	A(G) = |V(G)| — 1.
Dokaz. Naj bo n = |V(G)|. C e graf G vsebuje vozli s Ce stopnje n — 1, potem je oCitno 7(G) = 1 in yr(G) = 2.
ReCimo sedaj, da je 7 (G) = 1 in u G V (G) dominira G. Potem je f = (V(G) \ {u} , 0, {u}) 7R-funkCija grafa G (ker je G povezan in ima vsaj dve vozlisCi).
Naj bo nazadnje se 7r(G) = 2. Ce je f = (V(G) \ {u} , 0, {u}) yr-funkCija grafa G, potem mora biti vsako vozlisCe iz V (G) \ {u} sosednje z u, z drugimi besedami, u je stopnje n — 1. Po drugi strani pa je lahko tudi f = (V(G) \ {u, v} , {u, v} , 0) 7R-funkCija grafa G, katere vrednost je 2. To pa se lahko zgodi samo v primeru, ko je G graf K2 (G je povezan). V tem posebnem primeru sta obe vozli s Ci stopnje n — 1.	■
Trditev 6 ([5]). Naj bo G povezan graf na vsaj dveh vozliscih. Tedaj je 7r(G) = 3 natanko tedaj, ko je A(G) = |V(G)| — 2.
Dokaz. Naj bo 7R(G) = 3 in naj bo f = (Vo, Vi, V2) neka 7R-funkCija grafa G. Ce je V2 = 0, je oCitno |V(G)| = 3, in ker je G povezan, je to bodisi
P3 bodisi Ks. Ampak jr(P3) = jr(K3) = 2, kar je protislovje. Zato je |Vi| = IV2I = 1.
Naj bo u e V1 in v G V2. Po trditvi 2, točka 4, uv ni povezava grafa G, vsa druga vozliSča grafa G pa morajo biti po definiciji RDF sosednja z v. Zato je v stopnje | V(G)| - 2. Trditev 5 zagotavlja, da G nima vozlisča visje stopnje, to je stopnje | V(G)| — 1.
Da dokončamo dokaz, recimo, da je A(G) = |V(G)| — 2. Potem je po točki 5 trditve 2 yr(G) < |V(G)| — (|V(G)| — 2) + 1 = 3, ker velja trditev 5, pa je tudi 7r(G) > 3. Torej je 7r(G) = 3	-
Glede na zadnji trditvi je na prvi pogled videti, da bi lahko veljalo, da je Yr(G) = 4 natanko tedaj, ko je A(G) = | V(G)| — 3. Graf s slike 4 je tak, da je 7R(G) = 4, A(G) = 6, vozlisč pa ima kar 12. Vsaj v eno smer torej ta trditev ne drzi. Sami pa lahko preverite, ali velja, da iz A(G) = |V(G)| — 3 sledi, da je 7R(G) = 4.
O	O
Slika 4. Graf, imenovan dvojna zvezda.
LITERATURA
[1]	E. W. Chambers, B. Kinnersley, N. Price in D. B. West, Extremal problems for Roman domination, SIAM Journal on Discrete Mathematics 23 (2009), 1575-1586.
[2]	E. J. Cockayne, P. A. Dreyer, S. M. Hedetniemi in S. T. Hedetniemi, Roman, domination in graphs, Discrete Mathematics 278 (2004), 11-22.
[3]	D. Goncalves, A. Pinlou, M. Rao in S. Thomasse, The domination number of grids, SIAM Journal on Discrete Mathematics 25 (2011), 1443-1453.
[4]	M. A. Henning, Defending the roman empire from multiple attacks, Discrete Mathematics 271 (2003), 101-115.
[5]	T. Kraner Sumenjak, P. Pavlic in A. Tepeh, On the Roman domination in the lexicographic product of graphs, Discrete Applied Mathematics 160 (2012), 2030-2036.
[6]	C. S. ReVelle, Can you protect the Roman Empire, Johns Hopkins Magazine 49 (1997), 40.
[7]	C. S. ReVelle in K. E. Rosing, Defendens Imperium Romanum: a classical problem in military strategy, The American Mathematical Monthly 107 (2000), 585-594.
[8]	I. Stewart, Defend the Roman Empire!, Scientific American 281 (1999), 94-96.
[9]	Ancient Rome, www.en.wikipedia.org/wiki/Ancient_Rome, ogled september 2012.