2 papers
math.CO2016
On Vertex Rankings of Graphs and its Relatives
Ilan Karpas, Ofer Neiman, Shakhar Smorodinsky
A vertex ranking of a graph is an assignment of ranks (or colors) to the vertices of the graph, in such a way that any simple path connecting two vertices of equal rank, must conta…
cs.CC2016
Lower bounds for sensitivity of graph properties
Ilan Karpas
We prove that the sensitivity of any non-trivial graph property on vertices is at least , provided is sufficiently large.