On the toll number of a graph

A tolled walk T between two different, non-adjacent vertices u, v in a graph G is a walk in which u and v have exactly one neighbor. A toll interval between u, v is an element of V(G), T (u, v), is the set of all vertices of G that lie in some tolled u, v-walk. A set S subset of V(G) is t-convex if T (u, v) subset of S for any u, v is an element of S. The size of a maximum proper t-convex set S subset of V(G) is called the t-convexity number of a graph G and is denoted by c(t) (G). A vertex v is an element of V(G) is t-extreme if V(G)-{v} is a t-convex set of G. The toll number of G, tn(G), is the smallest size of a set S with boolean OR(u,v is an element of S) T (u, v) = V(G). In this paper we prove that tn(G) <= 6 in any prime graph G with diam(G) > 2. Then we present the exact value of the toll number of a cograph which implies that in any cograph G, tn(G) can be computed in polynomial time. Cographs are used to present the existence of a graph G of diameter 2 in which the difference between tn(G) and the number of t-extreme vertices is arbitrary large. Then we consider graphs with extreme toll number and give a characterization of graphs G with tn(G) is an element of {2, vertical bar V(G)vertical bar - 1, vertical bar V(G)vertical bar}. Finally we give a characterization of t-convex sets and prove that for a given k, deciding whether c(t)(G) >= k is NP-complete. (c) 2022 Elsevier B.V. All rights reserved.