Computing the hull number in toll convexity
share
A walk W between vertices u and v of a graph G is called a tolled walk between u and v if u, as well as v, has exactly one neighbour in W. A set S ⊆ V(G) is toll convex if the vertices contained in any tolled walk between two vertices of S are contained in S. The toll convex hull of S is the minimum toll convex set containing S. The toll hull number of G is the minimum cardinality of a set S such that the toll convex hull of S is V(G). The main contribution of this work is an algorithm for computing the toll hull number of a general graph in polynomial time.
READ FULL TEXT