Algebra poti in problemi dominacije na grafovskih produktih (Seminar DM)

Iz MaFiRaWiki

Algebra poti in problemi dominacije na grafovskih produktih

(Path algebra and domination problems on graph products)

Polona Pavlič


Torek, 4. december 2012, od 10-12, Plemljev seminar, Jadranska 19


Povzetek: S pomočjo algebre poti pokažemo, da se različni problemi dominacije na razredu poligrafov lahko rešijo v konstantnem času. Ker so posebni primeri poligrafov tudi grafovski produkti poti in ciklov, za kartezični in direktni produkt implementiramo algoritem in dobimo formule za dominantna, neodvisnostna dominantna ter rimska dominantna števila teh grafov, kjer je eden od faktorjev fiksen. Nadalje pokažemo, da se preučevane grafovske invariante na fasciagrafih in rotagrafih, pri katerih je monograf enak, lahko razlikujejo le za konstantno vrednost, natančneje, za končno število (različnih) konstant.

To je skupno delo z Janezom Žerovnikom.


Abstract: Using algebraic approach we show that different domination problems on the class of polygraphs can be solved in constant time. As polygraphs include products of paths and cycles, we implement the algorithm to get some closed expressions for the domination, the independent domination and the Roman domination number of the Cartesian and the direct product of paths and cycles, where the size of one factor is fixed. Additionally we show that the values of the investigated graph invariants on the fasciagraphs and the rotagraphs with the same monograph can only differ for a constant value.

This is joint work with Janez Žerovnik.

Glej tudi/See also


Seminar za diskretno matematiko

Osebna orodja