Nalaganje ...
Projekti / Programi vir: ARIS

Sodobne invariante grafov

Raziskovalna dejavnost

Koda Veda Področje Podpodročje
1.01.00  Naravoslovje  Matematika   

Koda Veda Področje
P110  Naravoslovno-matematične vede  Matematična logika, teorija množic, kombinatorika 

Koda Veda Področje
1.01  Naravoslovne vede  Matematika 
Ključne besede
barvanje grafa, dominacija grafa, vozliščno pokritje, metrična dimenzija, dominacijska igra, igra barvanja, igre na grafih
Vrednotenje (pravilnik)
vir: COBISS
Raziskovalci (17)
št. Evidenčna št. Ime in priimek Razisk. področje Vloga Obdobje Štev. publikacijŠtev. publikacij
1.  17005  dr. Boštjan Brešar  Matematika  Vodja  2018 - 2021  403 
2.  25993  dr. Sergio Cabello Justo  Matematika  Raziskovalec  2018 - 2021  218 
3.  50186  dr. Jasmina Ferme  Matematika  Raziskovalec  2018 - 2021  51 
4.  29919  dr. Marko Jakovac  Matematika  Raziskovalec  2018 - 2021  160 
5.  37839  dr. Aleksander Kelenc  Matematika  Raziskovalec  2018 - 2021  27 
6.  05949  dr. Sandi Klavžar  Matematika  Raziskovalec  2018 - 2021  1.177 
7.  22648  dr. Tadeja Kraner Šumenjak  Matematika  Raziskovalec  2018 - 2021  119 
8.  37403  dr. Tilen Marc  Matematika  Raziskovalec  2018 - 2021  47 
9.  51477  dr. Daša Mesarič Štesl  Matematika  Raziskovalec  2020 - 2021  20 
10.  01931  dr. Bojan Mohar  Matematika  Raziskovalec  2018 - 2021  1.002 
11.  20839  dr. Iztok Peterin  Matematika  Raziskovalec  2018 - 2021  352 
12.  32250  dr. Polona Repolusk  Interdisciplinarne raziskave  Raziskovalec  2018 - 2021  45 
13.  24904  dr. Simon Špacapan  Matematika  Raziskovalec  2018 - 2021  109 
14.  21821  dr. Andrej Taranenko  Matematika  Raziskovalec  2018 - 2021  132 
15.  37537  dr. Niko Tratnik  Matematika  Raziskovalec  2018 - 2021  155 
16.  11666  dr. Aleksander Vesel  Računalniško intenzivne metode in aplikacije  Raziskovalec  2018 - 2021  339 
17.  18504  dr. Petra Žigert Pleteršek  Matematika  Raziskovalec  2018 - 2021  174 
Organizacije (2)
št. Evidenčna št. Razisk. organizacija Kraj Matična številka Štev. publikacijŠtev. publikacij
1.  0101  Inštitut za matematiko, fiziko in mehaniko  Ljubljana  5055598000  20.216 
2.  2547  Univerza v Mariboru, Fakulteta za naravoslovje in matematiko  Maribor  5089638051  18.010 
Povzetek
Teorija grafov je hitro rastoče področje sodobne matematike in obravnava invariant grafov njen inherenten sestavni del. V tem projektu obravnavamo nekatere probleme, ki zadevajo klasične koncepte teorije grafov in njihovo obravnavo na naraven način kombiniramo s študijami nedavno vpeljanih in pogosto uporabnih grafovskih parametrov. Nekatere od novejših invariant, ki jih obravnavamo, so bile motivirane s praktičnimi problemi in aplikacijami, druge pa so bile vpeljane ob iskanju orodij za naskok na pomembne odprte domneve. Obravnavane invariante lahko razdelimo na več tipov in sicer, invariante barvanj, dominacijske invariante, invariante pokritij, dimenzijske invariante in igralne invariante grafov. Glavni cilji projekta so: (1) Podati nov vpogled in po možnosti tudi rešiti znamenite odprte probleme in domneve. Raziskave bodo vključevale variacije dominantnih števil kartezičnega produkta grafov (Vizingova domneva in rezultati Vizingovega tipa), kromatično število direktnega produkta grafov (Hedetniemijeva domneva), L(2,1) barvanja grafov z omejeno stopnjo (domneva Grigga in Yeha), b-kromatično število regularnih grafov (domneva Erdős-Farber-Lovász), dominantno število ravninskih skoraj triangulacij (domneva Mathesona in Tarjana), vozliščno pokritje k-poti v ravninskih grafih (šibka verzija Albertson-Bermanove domneve), pokritje grafa z geodetskimi potmi (povezava z Meynielovo domnevo), domneve o igralnem (celotnem) dominantnem številu, odprti problemi o igralnem kromatičnem številu in njegovih variacijah. (2) Nadaljevati raziskave nekaterih nedavno vpeljanih invariant grafov in prispevati pomemben napredek pri njihovi obravnavi. Invariante vključujejo, a niso omejene na različna barvanja in (mavrične) dominacijske invariante, b-kromatična števila, (sproščena) L(j,k) označevanja, pakirno kromatično število, različice invariant pokritij (še posebej omenimo vozliščno pokritje k-poti in krepko geodetsko število), različne tipe metrične dimenzije grafov in invariante, ki izhajajo iz iger na grafih kot npr. igralno kromatično število, indicirano kromatično število, igralno Grundyjevo število in igralno (celotno) dominantno število. (3) Prispevati celovite študije nekaterih med seboj prepletenih konceptov, ki bodo rezultirale v vsaj dveh preglednih člankih. V teh člankih nameravamo identificirati in poudariti osrednje odprte probleme kot tudi zastaviti nove odprte probleme. Pričakujemo, da bodo takšni pregledni članki imeli velik vpliv na pripadajoča raziskovalna področja. Osredotočili se bomo na več področij:  (i) dominacijske igre, za katere načrtujemo napisati monografijo;  (ii) pakirna barvanja in sorodni koncepti barvanj, porojeni z razdaljami v grafu; (iii) invariante dominacijskega tipa in njihovo vedenje v kartezičnem produktu grafov (rezultati Vizingovega tipa). (4) V načrtu tega projekta je monografija, ki bo obravnavala dominacijsko igro in sorodne igre ter invariante. Ta igra je bila vpeljana leta 2010 in je že v tem času postala ena najbolj široko obravnavanih iger na grafih. Pri pisanju knjige bosta sodelovala dva člana projektne skupine ter dva zunanja sodelavca, pri čemer smo bili vsi vključeni v raziskave dominacijske igre od samega začetka.
Pomen za razvoj znanosti
Projekt pripada temeljnim raziskavam s področja matematike in se s svojimi uporabnimi vidiki dotika nekaterih sorodnih področij kot na primer računalništva. Zastavljeni problemi so mednarodno pomembni, kar lahko utemeljimo z našimi publikacijami iz zadnjega obdobja kot tudi z odmevnostjo naših rezultatov. Načrtujemo naskok na nekatere pomembne matematične probleme, ki so odprti že vrsto let in katerih (popolna ali celo delna) rešitev bi pomenila znaten vpliv na razvoj raziskav v teoriji grafov in sorodnih področjih. Problemi, ki smo jih zastavili v projektu niso le nerešeni, temveč tudi relevantni, kar dokazuje število uveljavljenih matematikov, ki so se jih je že lotevali. V nekaterih primerih so problemi povezani z drugimi matematičnimi vejami (kot npr. z linearno algebro v primeru števila ničelne prisile), v spet drugih primerih pa so povezani z drugimi (uporabnimi) znanstvenimi področji (kot v primeru L(j,k) označitev, metrične dimenzije in drugih). Pričakujemo objavo več znanstvenih člankov v ključnih revijah s področja diskretne matematike, ki se bodo nanašali na vsebino projekta. Dobljene rezultate bomo predstavili na relevantnih mednarodnih konferencah.  Delo na projektu bo lahko služilo tudi kot odlična podpora za monografijo o dominacijskih igrah, kar je želen in izvedljiv cilj projekta. To utemeljuje hiter razvoj na tem področju in številni odzivi, ki ocenjujejo, da bi se monografija o pomembnem primeru igre na grafih na naraven način umestila v (neprazen) prostor med teorijo grafov in kombinatorično teorijo iger.
Pomen za razvoj Slovenije
The project belongs to basic research in the area of mathematics and with its applicable aspects touches some related fields such as computer science. Problems that we will work on are internationally important, which can be justified by our publications from the last period as well as with the impact of our results. We plan to attack some important long-standing mathematical problems, whose (complete or even partial) solutions would have considerable impact on research developments in graph theory and related areas. The problems that we propose to investigate are not only unsolved, but having in mind the number of established mathematicians that have considered them they are also relevant. In some cases, the problems are related to other mathematical disciplines (such as to linear algebra in the case of zero forcing numbers) and in some other cases they are connected to other (applicable) scientific areas (such as in the case of L(j,k) labelings, metric dimensions and others). We expect to publish several papers in key journals from the area of discrete mathematics related to the topics of the proposed project. We will also present our results at relevant international conferences.  The work on the project will also serve as a perfect support for the monograph concerning domination game(s), which is a desirable and realistic goal of the project, This can be justified by the quick development of the area, and a number of responses that a monograph about the important instance of graph game(s) would in a natural way be placed in the (non-empty) space between graph theory and combinatorial game theory.
Najpomembnejši znanstveni rezultati Vmesno poročilo
Najpomembnejši družbeno–ekonomsko in kulturno relevantni rezultati
Zgodovina ogledov
Priljubljeno