Computing the hull and interval numbers in the weakly toll convexity
share
A walk u_0u_1 … u_k-1u_k of a graph G is a weakly toll walk if u_0u_k ∉E(G), u_0u_i ∈ E(G) implies u_i = u_1, and u_ju_k∈ E(G) implies u_j=u_k-1. The weakly toll interval of a set S ⊆ V(G), denoted by I(S), is formed by S and the vertices belonging to some weakly toll walk between two vertices of S. Set S is weakly toll convex if I(S) = S. The weakly toll convex hull of S, denote by H(S), is the minimum weakly toll convex set containing S. The weakly toll interval number of G is the minimum cardinality of a set S ⊆ V(G) such that I(S) = V(G); and the weakly toll hull number of G is the minimum cardinality of a set S ⊆ V(G) such that H(S) = V(G). In this work, we show how to compute the weakly toll interval and the weakly toll hull numbers of a graph in polynomial time. In contrast, we show that determining the weakly toll convexity number of a graph G (the size of a maximum weakly toll convex set distinct from V(G)) is -hard.
READ FULL TEXT