Computing the hull and interval numbers in the weakly toll convexity

Abstract

A walk $u_0{u}_1\dots u_{k-1}{u}_k$ of a graph $G$ is a \textit{weakly toll walk} if $u_0{u}_k\notin E(G)$, $u_0{u}_i\in E(G)$ implies $u_i=u_1$, and $u_j{u}_k\in E(G)$ implies $u_j=u_{k-1}$. The {\em weakly toll interval} of a set $S\subseteq 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 {\it weakly toll convex} if $I(S)=S$. The {\em weakly toll convex hull} of $S$, denote by $H(S)$, is the minimum weakly toll convex set containing $S$. The {\em weakly toll interval number} of $G$ is the minimum cardinality of a set $S\subseteq V(G)$ such that $I(S)=V(G)$; and the {\em weakly toll hull number} of $G$ is the minimum cardinality of a set $S\subseteq 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 \NP-hard.