8 papers · 1 filter
Upper bounds for double Roman domination and -Roman domination of cylindrical graphs
Simon Brezovnik, Janez Žerovnik
Roman-type domination parameters form an important class of graph invariants that model protection and resource allocation problems on networks. Among them, -Roman domination…
Further results on \([k]\)-Roman domination on cylindrical grids \(C_m \Box P_n\)
Simon Brezovnik, Janez Žerovnik
In this paper, we study the -Roman domination number of cylindrical graphs . Our analysis begins with a general lower bound based on local neighborhood constrain…
-Roman domination on cylindrical grids
Simon Brezovnik, Janez Žerovnik
Roman domination and its higher-order extensions have attracted considerable attention due to their natural interpretation in terms of defensive resource allocation on networks. Th…
On rainbow domination of cubic graphs
Janez Žerovnik
The structure of minimal weight rainbow domination functions of cubic graphs are studied. Based on general observations for cubic graphs, generalized Petersen graphs are…
A fresh look to a randomized massively parallel graph coloring algorithm
Boštjan Gabrovšek, Janez Žerovnik
Petford and Welsh introduced a sequential heuristic algorithm for (approximately) solving the NP-hard graph coloring problem. The algorithm is based on the antivoter model and mimi…
Improved approximative multicoloring of hexagonal graphs
Janez Žerovnik
In 1999, McDiarmid and Reed conjectued that the approximation ratio of multichromatic number to weighted clique number asymptotically is the best possible for general weighte…
Self Similarities of the Tower of Hanoi Graphs and a proof of the Frame-Stewart Conjecture
Janez Žerovnik
Considering the symmetries and self similarity properties of the corresponding labeled graphs, it is shown that the minimal number of moves in the Tower of Hanoi game with p…
Improved upper bounds for vertex and edge fault diameters of Cartesian graph bundles
Janez Žerovnik, Rija Erveš
Mixed fault diameter of a graph , $ \D_{(a,b)}(G)$, is the maximal diameter of after deletion of any vertices and any edges. Special cases are the (vertex) fault dia…