66 citations · 323 across the 55 of their papers we have counts for
7 papers · 1 filter
Mind the Independence Gap
Tınaz Ekim, Didem Gözüpek, Ademir Hujdurović +1
The independence gap of a graph was introduced by Ekim et al. (2018) as a measure of how far a graph is from being well-covered. It is defined as the difference between the maximum…
A characterization of claw-free CIS graphs and new results on the order of CIS graphs
Liliana Alcón, Marisa Gutierrez, Martin Milanič
A graph is CIS if every maximal clique interesects every maximal stable set. Currently, no good characterization or recognition algorithm for the CIS graphs is known. We characteri…
Detecting strong cliques
Ademir Hujdurović, Martin Milanič, Bernard Ries
A strong clique in a graph is a clique intersecting every maximal independent set. We study the computational complexity of six algorithmic decision problems related to strong cliq…
Searching for square-complementary graphs: non-existence results and complexity of recognition
Ratko Darda, Martin Milanič, Miguel Pizaña
A graph is square-complementary (squco, for short) if its square and complement are isomorphic. We prove that there are no squco graphs with girth 6, that every bipartite graph is…
Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs
Endre Boros, Vladimir Gurvich, Martin Milanič
A hypergraph is said to be -Sperner if for every two hyperedges the smallest of their two set differences is of size one. We present several applications of -Sperner hypergra…
Bipartite Graphs of Small Readability
Rayan Chikhi, Vladan Jovicic, Stefan Kratsch +4
We study a parameter of bipartite graphs called readability, introduced by Chikhi et al. (Discrete Applied Mathematics, 2016) and motivated by applications of overlap graphs in bio…
New Algorithms for Weighted -Domination and Total -Domination Problems in Proper Interval Graphs
Nina Chiarelli, Tatiana Romina Hartinger, Valeria Alejandra Leoni +2
Given a positive integer , a -dominating set in a graph is a set of vertices such that every vertex not in the set has at least neighbors in the set. A total -domi…