Home > News > Polona Pavlič: Algebra poti in problemi dominacije na grafovskih produktih

Polona Pavlič: Algebra poti in problemi dominacije na grafovskih produktih

Date: 2. 12. 2012
Source: Discrete mathematics seminar
Torek, 4. 12. 2012 od 10h do 12h, Plemljev seminar, Jadranska 19

Algebra poti in problemi dominacije na grafovskih produktih

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.

Path algebra and domination problems on graph products

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.