Sodobne invariante grafov

ARRS št. projekta J1-9109

O projektu

Trajanje projekta

1. 7. 2018 – 30. 6. 2021

Financer

Vsebinski opis projekta

Več informacij

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:
    1. dominacijske igre, za katere načrtujemo napisati monografijo;
    2. pakirna barvanja in sorodni koncepti barvanj, porojeni z razdaljami v grafu;
    3. 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.

Projektna skupina

Več informacij
Ime in priimek Vloga Šifra raziskovalca Inštitucija
dr. Boštjan Brešar vodja projekta 17005 FNM UM, IMFM
dr. Aleksander Vesel raziskovalec 11666 FNM UM
dr. Petra Žigert Pleteršek raziskovalka 18504 FNM UM
dr. Tadeja Kraner Šumenjak raziskovalka 22648 FNM UM
dr. Andrej Taranenko raziskovalec 21821 FNM UM
dr. Marko Jakovac raziskovalec 29919 FNM UM
dr. Polona Repolusk raziskovalka 32250 FNM UM
dr. Niko Tratnik raziskovalec 37537 FNM UM
Aleksander Kelenc raziskovalec 37839 FNM UM
Jasmina Ferme raziskovalka 50186 FNM UM
dr. Bojan Mohar raziskovalec 01931 IMFM
dr. Sandi Klavžar raziskovalec 05949 IMFM
dr. Sergio Cabello Justo raziskovalec 25993 IMFM
dr. Iztok Peterin raziskovalec 20839 IMFM
dr. Simon Špacapan raziskovalec 24904 IMFM
dr. Tilen Marc raziskovalec 37403 IMFM
i

Članki

Prikaži izbor člankov projekta
  1. AZARIJA, Jernej, MARC, Tilen. There is no (95, 40, 12, 20) strongly regular graph. Journal of combinatorial designs, ISSN 1063-8539, Apr. 2020, vol. 28, iss. 4, str. 294-306. https://doi.org/10.1002/jcd.21696, doi: 10.1002/jcd.21696.    PDF
  2. BOŽOVIĆ, Dragana, PETERIN, Iztok. Efficient open domination in digraph products. Mathematics. Apr.. 2020, vol. 8, iss. 4, art. 496 (14 str.). ISSN 2227-7390.https://www.mdpi.com/2227-7390/8/4/496/pdf, DOI:10.3390/math8040496.
  3. BREŠAR, Boštjan, KOS, Tim, KRIVOŠ-BELLUŠ, Rastislav, SEMANIŠIN, Gabriel. Hitting subgraphs in P4-tidy graphs. Applied mathematics and Computation, July 2019, vol. 352, str. 211-219. https://doi.org/10.1016/j.amc.2019.01.074   PDF
  4. BREŠAR, Boštjan, KOS, Tim, TORRES, Pablo. Grundy domination and zero forcing in Kneser graphs. Ars mathematica contemporanea, 2019, vol. 17, no. 2, str. 419-430. ttps://doi.org/10.26493/1855-3974.1881.384   PDF
  5. BREŠAR, Boštjan, VALENCIA-PABON, Mario. Independence number of products of Kneser graphs. Discrete Mathematics, April 2019, vol. 342, iss. 4, str. 1017-1027. https://doi.org/10.1016/j.disc.2018.12.017   PDF
  6. BREŠAR, Boštjan, BUJTÁS, Csilla, GOLOGRANC, Tanja, KLAVŽAR, Sandi, KOŠMRLJ, Gašper, MARC, Tilen, PATKÓS, Balázs, TUZA, Zsolt, VIZER, Máté. The variety of domination games. Aequationes mathematicae, Dec. 2019, vol. 93, iss. 6, str. 1085-1109. https://doi.org/10.1007/s00010-019-00661-w   PDF
  7. BREŠAR, Boštjan, KLAVŽAR, Sandi, MOVARRAEI, Nazanin. Critical graphs for the chromatic edge-stability number. Discrete Mathematics, June 2020, vol. 343, iss. 6, art. 111845 [7 str.]. https://doi.org/10.1016/j.disc.2020.111845.   PDF
  8. BREŠAR, Boštjan, GASTINEAU, Nicolas, KLAVŽAR, Sandi, TOGNI, Olivier. Exact distance graphs of product graphs. Graphs and combinatorics, Nov. 2019, vol. 35, iss. 6, str. 1555-1569. https://doi.org/10.1007/s00373-019-02089-0.   PDF
  9. BREZOVNIK, Simon, KRANER ŠUMENJAK, Tadeja. Complexity of k-rainbow independent domination and some results on the lexicographic product of graphs. Applied mathematics and computation. [Print ed.]. 2019, vol. 349, str. 214-220, graf. prikazi. ISSN 0096-3003. DOI: 10.1016/j.amc.2018.12.009.   PDF
  10. BREZOVNIK, Simon, TRATNIK, Niko. New methods for calculating the degree distance and the Gutman index. MATCH Communications in Mathematical and in Computer Chemistry. 2019, vol. 82, no. 1, str. 111-132.http://match.pmf.kg.ac.rs/electronic_versions/Match82/n1/match82n1_111-132.pdf.
  11. BREZOVNIK, Simon, TRATNIK, Niko, ŽIGERT PLETERŠEK, Petra. Resonantly equivalent catacondensed even ring systems. MATCH Communications in Mathematical and in Computer Chemistry. 2019, vol. 82, no. 3, str. 625-638.  http://match.pmf.kg.ac.rs/electronic_versions/Match82/n3/match82n3_625-638.pdf.
  12. BREZOVNIK, Simon, TRATNIK, Niko, ŽIGERT PLETERŠEK, Petra. Resonance graphs of catacondensed even ring systems. Applied mathematics and computation. [Print ed.]. Jun. 2020, vol. 374, art. no. 125064, str. 1-9.  DOI: 10.1016/j.amc.2020.125064.   PDF
  13. BUJTÁS, Csilla, JAKOVAC, Marko. Relating the total domination number and the annihilation number of cactus graphs and block graphs. Ars mathematica contemporanea. 2019, vol. 16, no. 1, str. 183-202. https://amc-journal.eu/index.php/amc/article/download/1378/1284, DOI: 10.26493/1855-3974.1378.11d.
  14. GHAREGHANI, Narges, PETERIN, Iztok, SHARIFANI, Pouyeh. A note on bipartite graphs whose [1,k]-domination number equal to their number of vertices. Rocznik Akademii Górniczo-Hutniczej im. Stanisława Staszica.Opuscula Mathematica. 2020, vol. 40, no. 3, str. 375-382, ilustr. ISSN 1232-9274.https://doi.org/10.7494/OpMath.2020.40.3.375,https://www.opuscula.agh.edu.pl/vol40/3/art/opuscula_math_4020.pdf
  15. GOLOGRANC, Tanja, REPOLUSK, Polona. Toll number of the strong product of graphs. Discrete Mathematics. [Print ed.]. Mar. 2019, vol. 342, iss. 3, str. 807-814; https://doi.org/10.1016/j.disc.2018.11.007  PDF
  16. JAKOVAC, Marko. Relating the annihilation number and the 2-domination number of block graphs. Discrete applied mathematics. May 2019, vol. 260, str. 178-187. ISSN 0166-218X. DOI: 10.1016/j.dam.2019.01.020.    PDF
  17. KNAUER, Kolja, MARC, Tilen. On tope graphs of complexes of oriented matroids. Discrete & computational geometry, ISSN 0179-5376, March 2020, vol. 63, iss. 2, str. 377-417. https://doi.org/10.1007/s00454-019-00111-z, doi: 10.1007/s00454-019-00111-z    PDF
  18. KORŽE, Danilo, MARKUŠ, Žiga, VESEL, Aleksander. A heuristic approach for searching (d,n)-packing colorings of infinite lattices. Discrete applied mathematics, ISSN 0166-218X. [Print ed.], March 2019, vol. 257, str. 353-358. https://doi.org/10.1016/j.dam.2018.09.018, doi: 10.1016/j.dam.2018.09.018.   PDF
  19. TARANENKO, Andrej. Daisy cubes: a characterization and a generalization. European journal of combinatorics. March 2020, vol. 85. https://doi.org/10.1016/j.ejc.2019.103058.   PDF
  20. TRATNIK, Niko. Formula for calculating the Wiener polarity index with applications to benzenoid graphs and phenylenes. Journal of mathematical chemistry. 2019, vol. 57, iss. 1, str. 370-383. DOI: 10.1007/s10910-018-0957-7.   PDF
  21. TRATNIK, Niko, ŽIGERT PLETERŠEK, Petra. The edge-Hosoya polynomial of benzenoid chains. Journal of mathematical chemistry. 2019, vol. 57, iss. 1, str. 180-189. DOI: 10.1007/s10910-018-0942-1.   PDF
  22. TRATNIK, Niko. Computing weighted Szeged and PI indices from quotient graphs. International journal of quantum chemistry. 2019, vol. 119, no. 21, str. 1-13.  DOI: 10.1002/qua.26006.   PDF
  23. TRATNIK, Niko. Generalized cut method for computing the edge-Wiener index. Discrete applied mathematics. [Print ed.]. 2019, str. 1-12.  https://www.sciencedirect.com/science/article/pii/S0166218X19305098, DOI: 10.1016/j.dam.2019.11.002.   PDF
  24. VESEL, Aleksander. Cube-complements of generalized Fibonacci cubes. Discrete Mathematics, ISSN 0012-365X. [Print ed.], April 2019, vol. 342, iss. 4, str. 1139-1146. https://doi.org/10.1016/j.disc.2019.01.008, doi: 10.1016/j.disc.2019.01.008.    PDF
  25. ŽIGERT PLETERŠEK, Petra. The edge-Wiener index and the edge-hyper-Wiener index of phenylenes. Discrete applied mathematics. [Print ed.]. 28 Feb. 2019, vol. 255, str. 326-333. DOI: 10.1016/j.dam.2018.07.024.   PDF
Prikaži vse

Spodaj prikazan seznam je izbor člankov projekta.

  1. BREŠAR, Boštjan, KOS, Tim, KRIVOŠ-BELLUŠ, Rastislav, SEMANIŠIN, Gabriel. Hitting subgraphs in P4-tidy graphs. Applied mathematics and Computation, July 2019, vol. 352, str. 211-219.  PDF
  2. BREŠAR, Boštjan, KOS, Tim, TORRES, Pablo. Grundy domination and zero forcing in Kneser graphs. Ars mathematica contemporanea, 2019, vol. 17, no. 2, str. 419-430.  PDF
  3. BREŠAR, Boštjan, VALENCIA-PABON, Mario. Independence number of products of Kneser graphs. Discrete Mathematics, April 2019, vol. 342, iss. 4, str. 1017-1027.  PDF
  4. BREŠAR, Boštjan, BUJTÁS, Csilla, GOLOGRANC, Tanja, KLAVŽAR, Sandi, KOŠMRLJ, Gašper, MARC, Tilen, PATKÓS, Balázs, TUZA, Zsolt, VIZER, Máté. The variety of domination games. Aequationes mathematicae, Dec. 2019, vol. 93, iss. 6, str. 1085-1109.  PDF
  5. TARANENKO, Andrej. Daisy cubes: a characterization and a generalization. European journal of combinatorics. March 2020, vol. 85.
    https://doi.org/10.1016/j.ejc.2019.103058