66 citations · 323 across the 55 of their papers we have counts for
7 papers · 1 filter
On the complexity of the vector connectivity problem
Ferdinando Cicalese, Martin Milanič, Romeo Rizzi
We study a relaxation of the Vector Domination problem called Vector Connectivity (VecCon). Given a graph with a requirement for each vertex , VecCon asks for a minim…
Polynomial-time Algorithms for Weighted Efficient Domination Problems in AT-free Graphs and Dually Chordal Graphs
Andreas Brandstädt, Pavel Fičur, Arne Leitert +1
An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the vertex set of the graph. The minimum weight efficient…
Partial characterizations of 1-perfectly orientable graphs
Tatiana Romina Hartinger, Martin Milanič
We study the class of 1-perfectly orientable graphs, that is, graphs having an orientation in which every out-neighborhood induces a tournament. 1-perfectly orientable graphs form…
Equistarable graphs and counterexamples to three conjectures on equistable graphs
Martin Milanič, Nicolas Trotignon
Equistable graphs are graphs admitting positive weights on vertices such that a subset of vertices is a maximal stable set if and only if it is of total weight . In , Maha…
Vertex-transitive CIS graphs
Edward Dobson, Ademir Hujdurović, Martin Milanič +1
A CIS graph is a graph in which every maximal stable set and every maximal clique intersect. A graph is well-covered if all its maximal stable sets are of the same size, co-well-co…
How to go Viral: Cheaply and Quickly
Ferdinando Cicalese, Gennaro Cordasco, Luisa Gargano +3
Given a social network represented by a graph , we consider the problem of finding a bounded cardinality set of nodes with the property that the influence spreading from …
Graph classes with and without powers of bounded clique-width
Flavia Bonomo, Luciano N. Grippo, Martin Milanič +1
We initiate the study of graph classes of power-bounded clique-width, that is, graph classes for which there exist integers and such that the -th powers of the graphs…