Oznaka poročila: ARRS-RPROJ-ZP-2013/180 ZAKLJUČNO POROČILO RAZISKOVALNEGA PROJEKTA A. PODATKI O RAZISKOVALNEM PROJEKTU 1.Osnovni podatki o raziskovalnem projektu Šifra projekta Jl-2043 Naslov projekta Grafi in sorodne matematične strukture Vodja projekta 17005 Boštjan Brešar Tip projekta J Temeljni projekt Obseg raziskovalnih ur 5310 Cenovni razred A Trajanje projekta 05.2009 - 04.2012 Nosilna raziskovalna organizacija 101 Inštitut za matematiko, fiziko in mehaniko Raziskovalne organizacije -soizvajalke 2547 Univerza v Mariboru, Fakulteta za naravoslovje in matematiko Raziskovalno področje po šifrantu ARRS 1 NARAVOSLOVJE 1.01 Matematika 1.01.05 Teorija grafov Družbenoekonomski cilj 13 01 Naravoslovne vede - RiR financiran iz drugih virov (ne iz 13.01 SUF) 2.Raziskovalno področje po šifrantu FOS1 Šifra 1.01 -Veda 1 Naravoslovne vede - Področje 1.01 Matematika B. REZULTATI IN DOSEŽKI RAZISKOVALNEGA PROJEKTA 3.Povzetek raziskovalnega projekta2 SLO V tem projektu smo raziskovali povezave med grafi in nekaterimi drugimi matematičnimi strukturami. Te strukture vključujejo diskretne metrične prostore, delno urejene množice, abstraktne intervalske in konveksne prostore ter prostore vmesnosti, topološke strukture in geometrijske realizacije grafov v Evklidskih prostorih. Grafi v tej zvezi nastopajo kot grafi pokritij-neprimerljivosti (CI-grafi) delno urejenih množic, razredi grafov z metri čno porojenimi lastnostmi ter vložitve v ravnino ali druge ploskve. Na področju metrične teorije grafov smo raziskovali izometrične vložitve grafov v različne produktne strukture in s tem povezane grafovske dimenzije, geodetske in Steinerjeve množice ter medianske grafe in njihove poslošitve, v povezavi s kompleksi prizm. Na vseh teh področjih smo reševali znane odprte probleme ter nadalje razvijali in poglabljali teorije, v zvezi z geodetskimi množicah pa smo prispevali tudi pregledni članek v okviru monografije o kompleksnih omrežjih. Nadaljevali smo z raziskavami grafa pokritij-neprimerljivosti delno urejenih množic. V okviru topoloških konceptov na grafih smo raziskovali prekrižno število grafa, z ozirom na ravnino in ploskve višjih rodov. Prispevali smo številne nove rezultate na področju grafovskih invariant grafov, s poudarkom na grafovskih produktih. Izpostavimo predvsem obravnavo posebnih tipov barvanj (b-barvanja, Thuejeva barvanja, zvezdna barvanja) ter novejših dominacij skih invariant, kot na primer igerno dominacijsko število. V zvezi z dominacijo kartezičnega produkta smo objavili tudi pregledni članku o Vizingovi domnevi, ki vsebuje veliko novih pristopov in idej o tem problemu. ANG In this project connections between graphs and some other mathematical structures have been investigated. These structures include discrete metric spaces, partial orders, abstract interval and convex spaces, betweennes spaces, topological structures and geometric realizations of graphs in Euclidean spaces. Graphs in this relation appear as cover-incomparability graphs (CI-graphs) of posets, classes of graphs with metrically induced properties and embeddings in the plane or other surfaces. In the area of metric graph theory we investigated isometric embeddings of graphs into various product structures, and corresponding graph dimensions, geodetic and Steiner sets, and median graphs and their generalizations in relation with prism complexes. On all these areas we were solving well-known open problems and further developed and deepened the existing theories, and in relation with geodetic sets contributed a survey paper that appeared as a chapter in a monograph on complex networks. We continued with the study of cover-incomparability graphs of posets. In the context of topological concepts on graphs we investigated the crossing number of a graph, in relation with its plane embedding or with respect to surfaces of higher genera. Numerous new results were contributed in the area of graph invariants, with emphasis on graph products. Let us mention in particular the study of special types of colorings (b-colorings, Thue colorings, star colorings), and some recent domination invariants such as the game domination number. In relation with domination of the Cartesian graph product we also published a survey article on Vizing's conjecture that includes several new approaches and ideas on this problem. 4.Poročilo o realizaciji predloženega programa dela na raziskovalnem projektu3 Glavni namen tega projekta so bile raziskave v teorije grafov, v povezavi z diskretnimi metri čnimi prostori, prostori konveksnosti, geometrijskimi in topološkimi objekti, kot so poliedri, simplicialni kompleksi in kompleksi kock ter z delno urejenimi množicami. Področja, ki smo jih obravnavali, se paroma prepletajo, a se pri večini pojavlja metri čna teorija grafov ali grafovski produkti. V prvem odigra graf vlogo diskretnega metričnega prostora, v drugem pa so bile v ospredju raziskave grafovskih invariant. Na področju diskretnih metričnih prostorov smo nadaljevali z raziskavami izometričnih vložitev grafov v kartezične produkte grafov, v posebnem medianske grafe in njihove vložitve v hiperkocke. Tako smo študirali lastnosti, ki jih imajo maksimalne hiperkocke v medianskih grafih in preko različnih tipov kubnih grafov medianskih grafov okarakterizirali nekatere znane razrede grafov kot so npr. klični grafi. Obravnavali smo grafe semikock, ki so učinkovito orodje za računanje mrežne dimenzije grafa. Pokazali smo, da lahko vsak graf realiziramo kot graf semikock neke delne kocke in v podrobnostih obravnavali grafe semikock dreves. Izpeljali smo tudi algoritem časovno linearne zahtevnosti, ki na izometričen način vloži dano drevo v celoštevilsko mrežo najmanjše možne dimenzije in omogoča izračun mrežnih koordinat vozlišč drevesa v optimalnem času. Obravnavali smo vprašanje Fukude in Hande o tem, ali je vsaka uravnotežena delna kocka tudi harmonično uravnotežena. Dokazano je bilo, da je odgovor pozitiven, če je izometrična dimenzija grafa enaka njegovemu premeru, to pa je res za delne kocke izometrične dimenzije kvečjemu 6. Nadalje smo obravnavali funkcijo oddaljenosti v medianskem grafu in jo primerjali s funkcijo oddaljenosti v hiperkocki, v katero je izometrično vložen. Našli smo povezavo med vozlišči medianskega grafa, katerih funkcija oddaljenosti je največja, z antimediansko množico pripadajoče hiperkocke in ob tem dobili podroben strukturni opis antimedianskih množic z ozirom na parnost profilov. Te probleme smo obdelali tudi z algoritmičnega vidika. Obravnavali smo vprašanje Klavžarja in Mulderja o tem, ali inducirani cikel v križnem grafu medianskega grafa nujno porodi inducirano dvodelno kolo v originalnem grafu. Dokazano je bilo, da je odgovor pozitiven za cikle dolžin 4 in 5 in negativen za cikle daljših dolžin. Vpeljana je tudi izostritev ekspanzij skega postopka za delne kocke. V obsežnem članku smo obravnavali eno od osrednjih tem tega projekta, to je Steinerjeve intervale grafov. Dokazati nam je uspelo karakterizacijo tistega razreda grafov, v katerih Steinerjevi intervali na določenem fiksnem številu vozlišč sovpadajo z unijo geodetskih intervalov med temi vozlišči. Izkazalo se je presenetljivo dejstvo, da se le-ta ujema z razredom grafov, v katerih Steinerjevi intervali zadoščajo dvema tipoma lastnosti vmesnosti, čim je število vozlišč Steinerjevega intervala večje od 3. Za primer, ko tri vozlišča napenjajo Steinerjevo drevo, so ti razredi različni in jih tudi uspemo okarakterizirati. Na področju, ki povezuje grafe in delno urejene množice smo v novem članku na to temo obravnavali tiste delno urejene množice, katerih grafi pokritij-neprimerljivosti so tetivni. Okarakterizirali smo delne urejene množice, katerih grafi pokritij-neprimerljivosti so bločni grafi oziroma razcepljeni grafi na več načinov, med drugim tudi preko prepovedanih delno urejenih podmnožic. Rezultati so zanimivi tako za grafologe, ki se ukvarjajo s tetivnimi grafi kot tudi za raziskovalce delno urejenih množic. Ob zaključku projekta smo v članku, ki je še v postopku recenzije okarakterizirali kografe pokritij-neprimerljivosti med vsemi kografi in se približali končni rešitvi tega problema za tetivne grafe. Poleg tega smo odgovorili tudi na vprašanje, kdaj določene tranzitne funkcije na delno urejenih množicah sovpadajo. Na tri načine, tudi s prepovedanimi delno urejenimi podmnožicami, okarakteriziramo tiste delno urejene množice, v katerih standardna tranzitna funkcija sovpada s tranzitno funkcijo najkrajših poti njenega grafa pokritij-neprimerljivosti. Uspela nam je določitev geodetskega števila leksikografskih produktov grafov, izražena z novim konceptom geodominantne trojice, ki kombinira med seboj geodetsko in dominantno število. Z leksikografskim produktom pa se ukvarjamo tudi v drugem članku, v katerem opišemo konveksne množice različnih tipov v tem produktu. Med večje dosežke sodi rešitev dveh odprtih domnev na področju Steinerjevih množic. In sicer smo dokazali domnevo iz našega prejšnjega članka, ki pove, da 3-Steinerjevi intervali na povezanih grafih zadoščajo aksiomu vmesnosti (b2), če in samo če je vsak njegov blok geodetski graf z diametrom največ 2 (pri tem so geodetski grafi takšni grafi, pri katerih med vsakim parom vozlišč leži le ena geodetka). V članku o lokalni 3-Steinerjevi konveksnosti pa dokažemo pred tem odprto domnevo, ki so jo zastavili Henning, Nielsen in Oellermannova in pravi, da so v grafu vse krogle 3-Steinerjevo konveksne, če in samo če je vsak cikel dolžine vsaj 6 v njem dobro premostljiv in graf ne vsebuje dvojnega 4-cikla. Pregled najpomembnejših znanih rezultatov na področju geodetskih in Steinerjevih množic v grafih smo objavili kot posebno poglavje monografije "Structural Analysis of Complex Networks" pri priznani založbi. Študijo geodetskega števila grafov smo nadaljevali na leksikografskih produktih, kjer smo našli formulo za izračun geodetskega števila leksikografskega produkta poljubnega grafa z nepolnim grafom. V povezavi s konceptom geodetskega števila pa smo vpeljali in obravnavali tudi grafe periferij medianskih grafov in raziskali njihovo povezavo s križnimi grafi. Problem medianske in antimedianske množice v grafih ima praktično uporabo, saj ponazarja diskretni model za določitev naj bolj/naj manj zaželenih lokacij v omrežju. Na to temo smo v tem letu objavili dva članka in med drugim tudi predstavili dva učinkovita algoritma za določitev medianske (v enem tudi antimedianske) množice profilov v medianskih grafih. V zadnjem delu projekta smo poglobili raziskave obširnih posplošitev medianskih grafov, ki so v tesni zvezi z znanimi družinami kompleksov iz topologije in geometrijske teorije grup, kot so na primer sistolični kompleksi in CAT(0) kubni kompleksi. Vpeljali smo nov razred grafov in kompleksov, ki jih imenujemo bukolični grafi oziroma kompleksi in posplošijo obe prej omenjeni družini. Za ta razred smo pokazali več lepih in uporabnih lastnosti kot je na primer kontraktibilnost in obstoj fiksne prizme. Okarakterizirali smo tudi 2-skelete in 1-skelete teh kompleksov in dokazali, da so slednji natanko šibko modularni grafi, ki zadoščajo nekim lokalnim lastnostim v smislu prepovedanih podgrafov. Okarakterizirali smo jih tudi kot rektrakte kartezičnega produkta šibko mostovnih grafov in preko zaporedja zastraženih amalgamacij iz škatel s šibko mostovnimi faktorji. Rezultati veljajo za lokalno končne grafe, posplošitev na grafe in komplekse, v katerem dopuščamo tudi neskončne stopnje, a so prizme končnih dimenzij, pa je ostal odprt problem. Pri delu z invariantami na grafovskih produktih smo se ukvarjali s konveksnim pred-ovojnim številom v kartezičnem in leksikografskem produktu, s Thuejevim številom in Thuejevim indeksom v leksikografskem produktu in z b-kromatičnim številom v direktnem, krepkem in leksikografskem produktu. Konveksno pred-ovojno število v kartezičnem in leksikografskem produktu je sedaj natančno določeno. Za Thuejevo število/indeks so podane nove zgornje meje v odvisnosti od ustreznega števila v faktorjih. Poleg tega smo obravnavali b-kromatično število kubičnih grafov. Glavni novi rezultat na tem področju je, da imajo vsi kubični grafi, razen štirih izjem, ki jih navedemo, b-kromatično število enako 4. Nenazadnje na področju invariant omenimo tudi presenetljiv rezultat, do katerega smo se dokopali in sicer je to posplošitev Wilfove zgornje meje za kromatično število z ozirom na največjo lastno vrednost matrike sosednosti iz grafov na kontekst digrafov. Eden vrhuncev raziskav v zadnjih letih na področju dominacijske teorije grafov je pregledni članek o Vizingovi domnevi, ki poleg koristnega pregleda za raziskovalce na tem področju, nudi tudi nekatere nove smeri raziskovanja. Članek je bil objavljen v letu 2012 in ima že 6 čistih citatov. Na področju topološke teorije grafov smo dobili nekaj presenetljivih rezultatov. V povezavi z n-arnim prekrižnim številom, ki pomeni najmanjše število križanj v risbi grafi na orientabilni ploskvi roda n, smo rešili Salazarjev problem. In sicer smo dokazali, da za vsaki pozitivni števili a>b obstaja graf, katerega 0-arno prekrižno število je enako a, 1-narno enako b in je njegovo 2-arno prekrižno število enako 0. V drugem članku s tega področja smo analizirali problem prekrižnega števila skoraj-ravninskih grafov z različnih kombinatornih in algoritmičnih aspektov. Analiziramo tudi problem roda potenc Petersenovega grafa, gleda na produkt pika. V članku o degeneriranih in zvezdnih barvanjih smo združili topološke in verjetnostne motode, s pomočjo katerih smo dokazali rezultate, povezane z vprašanjem, ki ga je zastavil Borodin. In sicer dokažemo zgornjo mejo za kromatično število posebnega tipa barvanj ravninskih grafov, pri katerem unije barvnih razredov inducirajo degenerirane podgrafe. Večina (torej več kot polovica) rezultatov je bila dosežena v sodelovanju s tujimi partnerji, pri čemer so koristno vlogo odigrali tudi bilateralni projekti, ki smo jih v vmesnem času koristili in sicer bilaterale s Slovaško, Francijo, Indijo, Kitajsko ter poleg omenjenih tudi sodelovanje z uglednimi znanstveniki z ZDA, Južnoafriške republike in Kanade. S.Ocena stopnje realizacije programa dela na raziskovalnem projektu in zastavljenih raziskovalnih ciljev4 Realizacija ciljev projekta je potekala v skladu z načrti in jih na mnogih področjih tudi presegla, kar velja še posebej za raziskave na področju metrične teorije grafov. Kot presežke na tem področju omenimo rešitev dveh odprtih domnev s področja Steinerjevih intervalov in Steinerjeve funkcije ter nekaterih drugih metri čnih rezultatov, ki se nanašajo na leksikografski produkt. Nekateri od teh člankov ponujajo uporabne algoritmične rezultate, ki jim je sledila tudi implementacija nekaterih pripadajočih algoritmov. Delo v okviru tega projekta bo prepoznavno tudi zaradi preglednega članka o geodetskih množicah, ki smo ga objavili kot samostojno poglavje v monografiji o strukturi kompleknih imrežij. Tudi delo na raziskavah na področju povezav med delnimi urejenostmi in grafi je potekalo v skladu z načrti. Raziskave na področju grafovskih invariant lahko štejemo kot presežek zastavljenih ciljev. Problem dominantnega števila kartezičnega produkta v povezavi z Vizingovo domnevo smo povezali z obravnavo novo vpeljane igre na grafih z dvema igralcema t.i. igre dominacije, pri kateri smo v zadnjem letu objavili še dva nova članka. Eden vrhuncev je tudi pregledni članek o Vizingovi domnevi, ki poleg koristnega pregleda za raziskovalce na tem področju, nudi tudi nekatere nove smeri raziskovanja. Posebej izpostavimo tudi vpeljavo dveh novih invariant, ki sta že doživeli odmev v raziskovalni javnosti in sicer koncept vozliščnega pokritja k-poti ter koncept kvaziprirejanja v dvodelnih grafih. Obe novi invarianti, sicer z zelo različnih področij diskretne matematike, sta se porodili iz praktičnih problemov prenosa podatkov v brezžičnih senzorskih omrežjih. Tudi na tem področju gre za presežke zastavljenih ciljev. 6.Utemeljitev morebitnih sprememb programa raziskovalnega projekta oziroma sprememb, povečanja ali zmanjšanja sestave projektne skupine5 Sprememb vsebine raziskovalnega projekta ni bilo. V zadnjem letu tudi ni bilo nobenih sprememb v sestavi projektne skupine. 7.Najpomembnejši znanstveni rezultati projektne skupine6 Znanstveni dosežek 1. COBISS ID 16083801 Vir: COBISS.SI Naslov SLO Vizingova domneva: pregledni članek in novi rezultati ANG Vizing's conjecture: a survey and recent results Opis SLO Vizingova domneva je najpomembnejši odprt problem v dominacijski teoriji, ki je bil zastavljen že v letu 1968. Domneva trdi, da je dominacijsko število kartezičnega produkta dveh grafov vsaj tako veliko, kot je produkt dominacijskih števil faktorjev. Pri reševanju tega problema in razvoju teorije sorodnih problemov aktivno sodelujemo tudi nekateri člani naše projektne skupine. V članku naredimo pregled različnih pristopov k tej osrednji domnevi iz teorije grafovske dominacije in ob tem dokažemo tudi nekaj novih rezultatov. Tako so na primer pokazane nove lastnosti minimalnega protiprimera, dokazana je tudi nova spodnja meja za produkte grafov brez induciranega $K_{1,3}$ s poljubnimi grafi. Skozi celoten članek so obravnavani pripadajoči odprti problemi, vprašanja in sorodne domneve. ANG Vizing's conjecture is the most important open problem in domination theory, posed already in 1968. It asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. In solving this problem and at the development of the theory on related problems, some of the members of our group actively participate. In this paper we survey the approaches to this central conjecture from domination theory and give some new results along the way. For instance, several new properties of a minimal counterexample to the conjecture are obtained and a lower bound for the domination number is proved for products of claw-free graphs with arbitrary graphs. Open problems, questions and related conjectures are discussed throughout the paper. John Wiley; Journal of graph theory; 2012; Vol. 69, iss. 1; str. 46-76; Objavljeno v Impact Factor: 0.524;Srednja vrednost revije / Medium Category Impact Factor: 0.678; Avtorji / Authors: Brešar Boštjan, Dorbec Paul, Goddard Wayne, Hartnell Bert L., Henning Michael A., Klavžar Sandi, Rall Douglas F. Tipologija 1.02 Pregledni znanstveni članek 2. COBISS ID 16191577 Vir: COBISS.SI Naslov SLO Posplošitev madžarske metode in Hallovega izreka z uporabo v brezžičnih senzorskih omrežjih ANG A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks Opis SLO V tem članku obravnavamo različne probleme, ki zadevajo kvaziprirejanja in polprirejanja v dvodelnih grafih, ki posplošujejo klasični problem določitve popolnega prirejanja v dvodelnih grafih. Dokažemo posplošitev Hallovega poročnega izreka in predstavimo algoritem, ki reši problem določitve leksikografsko minimalnega $g(v)$-kvaziprirejanja. Ugotovimo, da je najti leksikografsko minimalno kvaziprirejanje ekvivalentno minimizaciji poljubne krepko konveksne funkcije na stopnjah A-strani kvaziprirejanja in uporabimo to dejstvo za dokaz splošnejše trditve. Predstavimo tudi aplikacijo v dizajnu optimalnega brezžičnega senzorskega omrežja, ki temelji na CDMA-tehnologiji. ANG In this paper, we consider various problems concerning quasi-matchings and semi-matchings in bipartite graphs, which generalize the classical problem of determining a perfect matching in bipartite graphs. We prove a generalization of Hall's marriage theorem, and present an algorithm that solves the problem of determining a lexicographically minimum $g$-quasi-matching. We obtain that finding a lexicographically minimum quasi-matching is equivalent to minimizing any strictly convex function on the degrees of the A-side of a quasi-matching and use this fact to prove a more general statement. We also present an application in designing optimal CDMA-based wireless sensor networks. Objavljeno v North-Holland; Discrete Applied Mathematics; 2012; Vol. 160, iss. 4-5; str. 460-470; Impact Factor: 0.795;Srednja vrednost revije / Medium Category Impact Factor: 0.89; Avtorji / Authors: Bokal Drago, Brešar Boštjan, Jerebic Janja Tipologija 1.01 Izvirni znanstveni članek 3. COBISS ID 15116377 Vir: COBISS.SI Naslov SLO Posplošitev Kneserjevega adicijskega izreka ANG A generalization of Kneser's Addition Theorem Opis SLO V članku avtorji združijo dve doslej ločeni področji v aditivni teoriji števil. Prvo gradi na posplošitvah izreka Erdös-Ginzbur-Ziv, drugo pa na fundamentalnem Kneserjevem izreku. Za njihov glavni izrek se izkaže, da ima za posledico več rezultatov, ki so bili doslej nepovezani. Čeprav ta članek predstavlja vrhunec nekega področja, pa iz njegovih rezultatov izhaja, da so možne še nekatere doslej neslutene posplošitve v smeri daljnosežne hipoteze Seymourja in Schrijverja, ki združuje algebrsko in kombinatorično plat aditivne teorije števil preko teorije matroidov. ANG In the paper the authors combine two so far separated areas of additive number theory. The first one builds on generalizations of Erdös-Ginzbur-Ziv theorem, while the second one on the fundamental Kneser's theorem. Their main theorem turns out to imply several results that were so far unrelated. Although this paper presents a climax of certain field, the results imply possibility of further generalizations, going to the direction of the far-reaching Seymour-Schrijver hypothesis that combines the algebraic and the combinatorial side of additive number theory through the matroid theory. Academic Press; Advances in mathematics; 2009; Vol. 220, no. 5; str. Objavljeno v 1531-1548; Impact Factor: 1.403;Srednja vrednost revije / Medium Category Impact Factor: 0.761; A': 1; Avtorji / Authors: DeVos Matt, Goddyn Luis, Mohar Bojan Tipologija 1.01 Izvirni znanstveni članek 4. COBISS ID 16079193 Vir: COBISS.SI Naslov SLO O lokalni 3-Steinerjevi konveksnosti ANG On a local 3-Steiner convexity Opis SLO Eno od glavnih področij projekta je obravnava različnih konveksnosti v povezavi z metrično teorijo grafov. V tem članku obravnavamo $g_3$=-konveksnost v grafu $, ki zajema tiste množice, pri katerih je Steinerjev interval poljubne trojice njihovih vozlišč v celoti vsebovan v njih. Henning, Nielsen in Oellermann (2009) so dokazali, da graf G, v katerem so j-krogle g_3-konveksne za vsak j>0, ne vsebuje hiše niti grafov dvojčkov C_4 kot induciranih podgrafov in je vsak cikel v G dolžine vsaj 6 dobro premostljiv. V tem članku dokažemo, da velja tudi obrat tega izreka, s čimer okarakteriziramo grafe z g_3-konveksnimi kroglami. ANG One of the main areas of the project is the investigation of various convexities, related with the metric graph theory. In this article we consider g_3-convexity in a graph G that consists of those sets, whose Steiner interval with respect to any of its three vertices lies in them. Henning et al. (2009) proved that if every j-ball for all j>0 is g_3-convex in a graph G, then G has no induced house nor twin C_4, and every cycle in G of length at least six is well-bridged. In this paper we show that the converse of this theorem is true, thus characterizing the graphs in which all balls are g_3-convex. Objavljeno v Academic Press; European journal of combinatorics; 2011; Vol. 32, no. 8; str. 1222-1235; Impact Factor: 0.677;Srednja vrednost revije / Medium Category Impact Factor: 0.678; Avtorji / Authors: Brešar Boštjan, Gologranc Tanja Tipologija 1.01 Izvirni znanstveni članek S.Najpomembnejši družbeno-ekonomski rezultati projektne skupine7 Družbeno-ekonomski dosežek 1. COBISS ID 15957337 Vir: COBISS.SI Naslov SLO Vabljena predavanja in organizacije minisimpozijev ANG Invited lectures and minisimposia organization Opis SLO Boštjan Brešar in Drago Bokal sta bila vabljena predavatelja in sta organizirala minisimpozija z naslovoma "Metric graph theory" in "Crossing numbers" v okviru ugledne mednarodne konference "7th Slovenian international conference on graph theory," ki je potekala na Bledu. Bojan Mohar je bil v programskem odboru te konference. Boštjan Brešar je imel v okviru "International Conference on Recent Trends in Graph Theory and Combinatorics (ICRTGC-2010) : a Satellite Conference of the International Congress of Mathematicians (ICM) 2010 : 12-15, August 2010, Cochin, India" enourno vabljeno predavanje z naslovom "On the local Steiner 3-convexity." Boštjan Brešar and Drago Bokal were invited lecturers and organized minisymposia entitled "Metric graph theory" and "Crossing numbers", respectively, in the frame of the reputable conference "7th Slovenian international conference on graph theory," held in Bledu. Bojan Mohar was in the program committe of this conference. ANG Boštjan Brešar gave a one hour invited lecture "On the local Steiner 3-convexity" at the "International Conference on Recent Trends in Graph Theory and Combinatorics (ICRTGC-2010) : a Satellite Conference of the International Congress of Mathematicians (ICM) 2010 : 12-15, August 2010, Cochin, India." Šifra B.04 Vabljeno predavanje Objavljeno v UP FAMNIT;UP PINT; Abstracts of the 7th Slovenian international conference on graph theory, Bled, Slovenia, 19-25 June 2011; 2011; Str. 31; Avtorji / Authors: Brešar Boštjan Tipologija 1.12 Objavljeni povzetek znanstvenega prispevka na konferenci 2. COBISS ID Vir: vpis v poročilo Naslov SLO Članstvo v uredniškem odboru ANG Editorial board membership Opis SLO Bojan Mohar je: - področni urednik (associate editor) revije Discrete Mathematics, - član uredniškega odbora revije Journal of Combinatorial Theory Series B, - član uredniškega odbora revije Linear and Multilinear Algebra, - član uredniškega odbora revije MATCH Communications in Mathematical and in Computer Chemistry, - član uredniškega odbora revije Ars Mathematica Contemporanea. Bojan Mohar is - associate editor of Discrete Mathematics - a member of the editorial board of Journal of Combinatorial Theory Series B, - a member of the editorial board of Linear and Multilinear Algebra, - a member of the editorial board of MATCH Communications in Mathematical and Computer Chemistry, - a member of the editorial board of Ars Mathematica Contemporanea. ANG Šifra C.04 Uredništvo mednarodne revije Objavljeno v Redno objavljano v posameznih številkah revij Tipologija 4.00 Sekundarno avtorstvo 3. COBISS ID Vir: vpis v poročilo Naslov SLO Doktorske disertacije nastale v povezavi s projektom ANG Doctoral theses in the relation with the project Opis SLO Pod (so) mentorstvom Boštjana Brešarja so v povezavi s projektom doktorirali: A. Tepeh: Posplošitve medianskih grafov in geodetsko število T. Kraner Šumenjak: Nekateri presečni koncepti in invariante v metrični teoriji grafov K. Benkič: Prometno uravnoteženi usmerjevalni algoritmi za brezžična senzorska omrežja Mlada raziskovalka Tanja Gologranc pa je prijavila temo z naslovom Primeri uporabe mostovnih grafov in njihovih posplošitev, iz katere bo doktorirala predvidoma prihodnje leto. ANG Under the supervision of Boštjan Brešar, the following PhD theses in the relation with the project have been completed: A. Tepeh: Generalizations of median graphs and geodetic number T. Kraner Šumenjak: Some intersection concepts and invariants in metric graph theory K. Benkič: Traffic balanced routing algorithms in wireless sensor networks Young researcher Tanja Gologranc has comitted a proposal for a doctoral thesis entitled Instances of applications of bridged graphs and their applications, which she is supposed to defend next year. Šifra D.09 Mentorstvo doktorandom Objavljeno v Objavljeno v osebni bibliografiji mentorja in doktorandov Tipologija 4.00 Sekundarno avtorstvo 9.Drugi pomembni rezultati projetne skupine8 lO.Pomen raziskovalnih rezultatov projektne skupine9 10.1.Pomen za razvoj znanosti10 SLO Projekt sodi med temeljne raziskave s področja matematike. Vsebina projekta pripada pomembnemu delu teorije grafov in se v veliki meri povezuje z več drugimi področji kot so denimo teorija konveksnosti, kombinatorika delno urejenih množic, diskretni metrični prostori, teorija algoritmov in drugo. Problemi, ki si jih zastavljamo, so mednarodno pomembni, kar med drugim dokazuje naša bibliografija v zadnjem obdobju in odmevnost rezultatov. Rezultate projekta smo objavili v uglednih mednarodnih revijah in predstavili na mednarodnih znanstvenih konferencah, tudi v okviru plenarnih predavanj. S tem se krepi že sedaj visok ugled slovenske šole teorije grafov. ANG This project contributes to fundamental research in the area of mathematics. Its contents belongs to important areas of graph theory, and largely connects with several other areas such as convexity theory, combinatorics of partial ordered sets, discrete metric spaces, theory of algorithms and others. Problems that were posed are internationally significant as our recent biblografy and its citations show. The results of the project have been published in reputable international journals and presented at international scientific conferences, also as plenary lectures. By all these the high reputation of Slovenian graph theory school is further strengthened. 10.2.Pomen za razvoj Slovenije11 SLO Raziskovalni projekt je namenjen predvsem razvoju matematike in s tem dviga nivo te temeljne znanosti v Sloveniji in tudi širše. Ker je matematika prisotna na mnogih drugih področjih, kvalitetno raziskovanje matematike posredno, a pomembno vpliva tudi na razvoj vrste drugih disciplin. Dobljeni rezultati so predvsem teoretični. Kljub temu pa imajo veliko potencialno uporabo v praksi, kar se posebej nanaša na naša algoritmična in optimizacijska raziskovanja. V dele projekta smo vključevali tudi mlade raziskovalce in se povezovali s sodelavci iz mnogih držav širom sveta in s tem utrjujemo in nadgrajujemo kvalitetno raziskovalno delo s področja matematike v Sloveniji. ANG The aim of this research project is mainly in the development of mathematics and by this it increases the level of this fundamental science in Slovenia and also internationally. Since mathematics is a part of many other areas, the quality research in mathematics implicitly, but significantly impacts the development of numerous other disciplines. Obtained results are mainly theoretical. In spite of this they contain a large potential for practical applications, which in particular holds for our algortihmic and optimization research. In several parts of the project we engaged also young researchers, and cooperated with colleagues from many world countries, thus firming as well as improving the quality research in the area of mathematics in Slovenia. ll.Samo za aplikativne projekte in podoktorske projekte iz gospodarstva! Označite, katerega od navedenih ciljev ste si zastavili pri projektu, katere konkretne rezultate ste dosegli in v kakšni meri so doseženi rezultati uporabljeni Cilj F.01 Pridobitev novih praktičnih znanj, informacij in veščin Zastavljen cilj o da o ne Rezultat 1 d Uporaba rezultatov 1 d F.02 Pridobitev novih znanstvenih spoznanj Zastavljen cilj o da o ne Rezultat d Uporaba rezultatov d F.03 Večja usposobljenost raziskovalno-razvojnega osebja Zastavljen cilj o da o ne Rezultat d Uporaba rezultatov F.04 Dvig tehnološke ravni Zastavljen cilj o da o ne Rezultat d Uporaba rezultatov d F.05 Sposobnost za začetek novega tehnološkega razvoja Zastavljen cilj o da o ne Rezultat I d Uporaba rezultatov 1 d F.06 Razvoj novega izdelka Zastavljen cilj o da o ne Rezultat I d Uporaba rezultatov F.07 Izboljšanje obstoječega izdelka Zastavljen cilj o da o ne Rezultat d Uporaba rezultatov d F.08 Razvoj in izdelava prototipa Zastavljen cilj o da o ne Rezultat d Uporaba rezultatov d F.09 Razvoj novega tehnološkega procesa oz. tehnologije Zastavljen cilj o da o ne Rezultat d Uporaba rezultatov 1 d F.10 Izboljšanje obstoječega tehnološkega procesa oz. tehnologije Zastavljen cilj o da o ne Rezultat d Uporaba rezultatov d F.11 Razvoj nove storitve Zastavljen cilj o da o ne Rezultat d Uporaba rezultatov d F.12 Izboljšanje obstoječe storitve Zastavljen cilj o da o ne Rezultat d Uporaba rezultatov d F.13 Razvoj novih proizvodnih metod in instrumentov oz. proizvodnih procesov Zastavljen cilj o da o ne Rezultat Uporaba rezultatov d F.14 Izboljšanje obstoječih proizvodnih metod in instrumentov oz. proizvodnih procesov Zastavljen cilj o da o ne Rezultat d Uporaba rezultatov d F.15 Razvoj novega informacijskega sistema/podatkovnih baz Zastavljen cilj o da o ne Rezultat d Uporaba rezultatov d F.16 Izboljšanje obstoječega informacijskega sistema/podatkovnih baz Zastavljen cilj o da o ne Rezultat d Uporaba rezultatov d F.17 Prenos obstoječih tehnologij, znanj, metod in postopkov v prakso Zastavljen cilj o da o ne Rezultat I d Uporaba rezultatov d F.18 Posredovanje novih znanj neposrednim uporabnikom (seminarji, forumi, konference) Zastavljen cilj o da o ne Rezultat I d Uporaba rezultatov 1 d F.19 Znanje, ki vodi k ustanovitvi novega podjetja ("spin off") Zastavljen cilj o da o ne Rezultat d Uporaba rezultatov d F.20 Ustanovitev novega podjetja ("spin off") Zastavljen cilj o da o ne Rezultat d Uporaba rezultatov d F.21 Razvoj novih zdravstvenih/diagnostičnih metod/postopkov Zastavljen cilj o da o ne Rezultat Uporaba rezultatov F.22 Izboljšanje obstoječih zdravstvenih/diagnostičnih metod/postopkov Zastavljen cilj o da o ne Rezultat I d Uporaba rezultatov 1 d F.23 Razvoj novih sistemskih, normativnih, programskih in metodoloških rešitev Zastavljen cilj o da o ne Rezultat d Uporaba rezultatov d F.24 Izboljšanje obstoječih sistemskih, normativnih, programskih in metodoloških rešitev Zastavljen cilj o da o ne Rezultat d Uporaba rezultatov d F.25 Razvoj novih organizacijskih in upravljavskih rešitev Zastavljen cilj o da o ne Rezultat d Uporaba rezultatov d F.26 Izboljšanje obstoječih organizacijskih in upravljavskih rešitev 1 Zastavljen cilj O da o ne Rezultat d Uporaba rezultatov d F.27 Prispevek k ohranjanju/varovanje naravne in kulturne dediščine Zastavljen cilj O da o ne Rezultat d Uporaba rezultatov d F.28 Priprava/organizacija razstave Zastavljen cilj O da o ne Rezultat d Uporaba rezultatov d F.29 Prispevek k razvoju nacionalne kulturne identitete Zastavljen cilj o da o ne Rezultat Uporaba rezultatov d F.30 Strokovna ocena stanja Zastavljen cilj O da o ne Rezultat d Uporaba rezultatov d F.31 Razvoj standardov Zastavljen cilj O da o ne Rezultat d Uporaba rezultatov d F.32 Mednarodni patent Zastavljen cilj O da o ne Rezultat d Uporaba rezultatov d F.33 Patent v Sloveniji Zastavljen cilj o da o ne Rezultat Uporaba rezultatov d F.34 Svetovalna dejavnost Zastavljen cilj O da o ne Rezultat d Uporaba rezultatov 1 d F.35 Drugo Zastavljen cilj o da o ne Rezultat d Uporaba rezultatov 1 d Komentar 12.Samo za aplikativne projekte in podoktorske projekte iz gospodarstva! Označite potencialne vplive oziroma učinke vaših rezultatov na navedena področja Vpliv Ni vpliva Majhen vpliv Srednji vpliv Velik vpliv G.01 Razvoj visokošolskega izobraževanja G.01.01. Razvoj dodiplomskega izobraževanja O o o o G.01.02. Razvoj podiplomskega izobraževanja o o o o G.01.03. Drugo: o o o o G.02 Gospodarski razvoj G.02.01 Razširitev ponudbe novih izdelkov/storitev na trgu o o o o G.02.02. Širitev obstoječih trgov o o o o G.02.03. Znižanje stroškov proizvodnje o o o o G.02.04. Zmanjšanje porabe materialov in energije o o o o G.02.05. Razširitev področja dejavnosti o o o o G.02.06. Večja konkurenčna sposobnost o o o o G.02.07. Večji delež izvoza o o o o G.02.08. Povečanje dobička o o o o G.02.09. Nova delovna mesta o o o o G.02.10. Dvig izobrazbene strukture zaposlenih o o o o G.02.11. Nov investicijski zagon o o o o G.02.12. Drugo: o o o o G.03 Tehnološki razvoj G.03.01. Tehnološka razširitev/posodobitev dejavnosti o o o o G.03.02. Tehnološko prestrukturiranje dejavnosti o o o o G.03.03. Uvajanje novih tehnologij o o o o G.03.04. Drugo: o o o o G.04 Družbeni razvoj G.04.01 Dvig kvalitete življenja o o o o G.04.02. Izboljšanje vodenja in upravljanja o o o o G.04.03. Izboljšanje delovanja administracije o o o o in javne uprave G.04.04. Razvoj socialnih dejavnosti O o o o G.04.05. Razvoj civilne družbe o o o o G.04.06. Drugo: o o o o G.05. Ohranjanje in razvoj nacionalne naravne in kulturne dediščine in identitete o o o o G.06. Varovanje okolja in trajnostni razvoj o o o o G.07 Razvoj družbene infrastrukture G.07.01. Informacijsko-komunikacijska infrastruktura o o o o G.07.02. Prometna infrastruktura o o o o G.07.03. Energetska infrastruktura o o o o G.07.04. Drugo: o o o o G.08. Varovanje zdravja in razvoj zdravstvenega varstva o o o o G.09. Drugo: o o o o Komentar 13.Pomen raziskovanja za sofinancerje12 Sofinancer 1. Naziv Naslov Vrednost sofinanciranja za celotno obdobje trajanja projekta je znašala: EUR Odstotek od utemeljenih stroškov projekta: % Najpomembnejši rezultati raziskovanja za sofinancerja Šifra 1. 2. 3. 4. 5. Komentar Ocena 14.Izjemni dosežek v letu 201213 14.1. Izjemni znanstveni dosežek Objava odmevnega preglednega članka, Vir: COBISS ID 16083801. Pregledni Članek "Vizing's conjecture: a survey and recent results" mednarodne skupine avtorjev B. Brešar, P. Dorbec, W. Goddard, B. L. Hartnell, M. A. Henning, S. Klavžar, D. F. Rall je leta 2012 izšel v osrednji reviji s področja teorije grafov Journal of Graph Theory. Po podatkih revije je med štirimi največkrat dostopanimi članki te revije v letu 2012, poleg tega je v letu 2012 članek zabeležil že 6 čistih citatov, kar je za članek s področja matematike zavidljiva številka. Glej priponko. 14.2. Izjemni družbeno-ekonomski dosežek C. IZJAVE Podpisani izjavljam/o, da: • so vsi podatki, ki jih navajamo v poročilu, resnični in točni • se strinjamo z obdelavo podatkov v skladu z zakonodajo o varstvu osebnih podatkov za potrebe ocenjevanja ter obdelavo teh podatkov za evidence ARRS • so vsi podatki v obrazcu v elektronski obliki identični podatkom v obrazcu v pisni obliki • so z vsebino zaključnega poročila seznanjeni in se strinjajo vsi soizvajalci projekta Podpisi: zastopnik oz. pooblaščena oseba in vodja raziskovalnega projekta: raziskovalne organizacije: i Inštitut za matematiko, fiziko in Boštjan Brešar mehaniko ŽIG Kraj in datum: Maribor |12.3.2013" Oznaka prijave: ARRS-RPROJ-ZP-2013/ 180 1 Opredelite raziskovalno področje po klasifikaciji FOS 2007 (Fields of Science). Prevajalna tabela med raziskovalnimi področji po klasifikaciji ARRS ter po klasifikaciji FOS 2007 (Fields of Science) s kategorijami WOS (Web of Science) kot podpodročji je dostopna na spletni strani agencije (http://www.arrs.gov.si/sl/gradivo/sifranti/preslik-vpp-fos-wos.asp). Nazaj 2 Napišite povzetek raziskovalnega projekta (največ 3.000 znakov v slovenskem in angleškem jeziku) Nazaj 3 Napišite kratko vsebinsko poročilo, kjer boste predstavili raziskovalno hipotezo in opis raziskovanja. Navedite ključne ugotovitve, znanstvena spoznanja, rezultate in učinke raziskovalnega projekta in njihovo uporabo ter sodelovanje s tujimi partnerji. Največ 12.000 znakov vključno s presledki (približno dve strani, velikost pisave 11). Nazaj 4 Realizacija raziskovalne hipoteze. Največ 3.000 znakov vključno s presledki (približno pol strani, velikost pisave 11) Nazaj 5 V primeru bistvenih odstopanj in sprememb od predvidenega programa raziskovalnega projekta, kot je bil zapisan v predlogu raziskovalnega projekta oziroma v primeru sprememb, povečanja ali zmanjšanja sestave projektne skupine v zadnjem letu izvajanja projekta, napišite obrazložitev. V primeru, da sprememb ni bilo, to navedite. Največ 6.000 znakov vključno s presledki (približno ena stran, velikost pisave 11). Nazaj 6 Navedite znanstvene dosežke, ki so nastali v okviru tega projekta. Raziskovalni dosežek iz obdobja izvajanja projekta (do oddaje zaključnega poročila) vpišete tako, da izpolnite COBISS kodo dosežka - sistem nato sam izpolni naslov objave, naziv, IF in srednjo vrednost revije, naziv FOS področja ter podatek, ali je dosežek uvrščen v A'' ali A'. Nazaj 7 Navedite družbeno-ekonomske dosežke, ki so nastali v okviru tega projekta. Družbeno-ekonomski rezultat iz obdobja izvajanja projekta (do oddaje zaključnega poročila) vpišete tako, da izpolnite COBISS kodo dosežka - sistem nato sam izpolni naslov objave, naziv, IF in srednjo vrednost revije, naziv FOS področja ter podatek, ali je dosežek uvrščen v A'' ali A'. Družbeno-ekonomski dosežek je po svoji strukturi drugačen kot znanstveni dosežek. Povzetek znanstvenega dosežka je praviloma povzetek bibliografske enote (članka, knjige), v kateri je dosežek objavljen. Povzetek družbeno-ekonomskega dosežka praviloma ni povzetek bibliografske enote, ki ta dosežek dokumentira, ker je dosežek sklop več rezultatov raziskovanja, ki je lahko dokumentiran v različnih bibliografskih enotah. COBISS ID zato ni enoznačen, izjemoma pa ga lahko tudi ni (npr. prehod mlajših sodelavcev v gospodarstvo na pomembnih raziskovalnih nalogah, ali ustanovitev podjetja kot rezultat projekta _ - v obeh primerih ni COBISS ID). Nazaj 8 Navedite rezultate raziskovalnega projekta iz obdobja izvajanja projekta (do oddaje zaključnega poročila) v primeru, da katerega od rezultatov ni mogoče navesti v točkah 7 in 8 (npr. ker se ga v sistemu COBISS ne vodi). Največ 2.000 znakov, vključno s presledki. Nazaj 9 Pomen raziskovalnih rezultatov za razvoj znanosti in za razvoj Slovenije bo objavljen na spletni strani: http://sicris.izum.si/ za posamezen projekt, ki je predmet poročanja Nazaj 10 Največ 4.000 znakov, vključno s presledki Nazaj 11 Največ 4.000 znakov, vključno s presledki Nazaj 12 Rubrike izpolnite / prepišite skladno z obrazcem "izjava sofinancerja" http://www.arrs.gov.si/sl/progproj/rproj/gradivo/, ki ga mora izpolniti sofinancer. Podpisan obrazec "Izjava sofinancerja" pridobi in hrani nosilna raziskovalna organizacija - izvajalka projekta. Nazaj 13 Navedite en izjemni znanstveni dosežek in/ali en izjemni družbeno-ekonomski dosežek raziskovalnega projekta v letu 2012 (največ 1000 znakov, vključno s presledki). Za dosežek pripravite diapozitiv, ki vsebuje sliko ali drugo slikovno gradivo v zvezi z izjemnim dosežkom (velikost pisave najmanj 16, približno pol strani) in opis izjemnega dosežka (velikost pisave 12, približno pol strani). Diapozitiv/-a priložite kot priponko/-i k temu poročilu. Vzorec diapozitiva je objavljen na spletni strani ARRS http://www.arrs.gov.si/sl/gradivo/, predstavitve dosežkov za pretekla leta pa so objavljena na spletni strani http://www.arrs.gov.si/sl/analize/dosez/. Nazaj Obrazec: ARRS-RPROJ-ZP/2013 v1.00 95-C5-A2-F1-7E-6E-04-86-1C-A4-FE-56-E6-DF-81-08-A3-2F-3A-FE NARAVOSLOVJE Področje: 1.01 - Matematika Dosežek 1: Objava odmevnega preglednega članka, Vir: COBISS ID 16083801 Pregledni Članek "Vizing's conjecture: a survey and recent results" mednarodne skupine avtorjev B. Brešar, P. Dorbec, W. Goddard, B. L. Hartnell, M. A. Henning, S. Klavžar, D. F. Rall je leta 2012 izšel v osrednji reviji s področja teorije grafov Journal of Graph Theory. Po podatkih revije je med štirimi največkrat dostopanimi članki te revije v letu 2012, poleg tega je v letu 2012 članek zabeležil že 6 čistih citatov, kar je za članek s področja matematike zavidljiva številka. Vizingova domneva je najpomembnejši odprt problem v dominacijski teoriji, ki ga je Vadim G. Vizing zastavil leta 1968. Domneva trdi, da je dominantno število kartezičnega produkta dveh grafov vsaj tolikšno kot je produkt dominantnih števil obeh faktorjev. Pri reševanju tega problema in razvoju teorije sorodnih problemov aktivno sodelujemo tudi nekateri člani projektne skupine. V članku naredimo pregled različnih pristopov k tej osrednji domnevi iz teorije grafovske dominacije in ob tem dokažemo tudi nekaj novih rezultatov. Tako so na primer pokazane nove lastnosti minimalnega protiprimera, če le-ta obstaja, dokazana pa je tudi nova spodnja meja za produkte grafov brez induciranega K1,3 s poljubnimi grafi. Skozi celoten članek so obravnavani pripadajoči odprti problemi, vprašanja in sorodne domneve. Čeprav so bili do sedaj narejeni mnogi različni pristopi k reševanju te domneve (med drugim je bila dokazana tudi za tetivne grafe) in so znani tudi pomembni delni rezultati, pa se zdi, da je dokončna rešitev domneve še oddaljena. Ob tem se porajajo novi pristopi in metode v dominacijski teoriji ter rešujejo sorodni problemi različnih dominacijskih invariant na grafovskih produktih, pri katerih slovenska šola teorije grafov igra eno najvidnejših vlog.