Path Security Number

 

(joint work with Boštjan Brešar, František Kardoš and Ján Katrenič)

Given a positive integer k, we consider a partition of vertices of a graph G into two classes U and W in such a way that the order of each path induced by the vertices of class U is at most k-1. The path security number P(G,k) is defined as the minimum cardinality of the set W among all possible  partitions of the vertices of G with given properties. We present results on the complexity of the defined problems and some estimations and bounds for path security number for special classes of graphs (trees, outerplanar, cubic, …).