Geodetic Number versus Hull Number in $P_3$-Convexity
Carmen Cecilia Centeno, Lúcia Draque Penso, Dieter Rautenbach, Vinícius G. Pereira de Sá · SIAM Journal on Discrete Mathematics · 2013
We study the graphs $G$ for which the hull number $h(G)$ and the geodetic number $g(G)$ with respect to $P_3$-convexity coincide. These two parameters correspond to the minimum cardinality of a set $U$ of vertices of $G$ such that the simple expansion process which iteratively adds to $U$ all vertices outside of $U$ having two neighbors in $U$ produces the whole vertex set of $G$ either eventually or after one iteration, respectively. We establish numerous structural properties of the graphs $G$ with $h(G)=g(G)$, allowing for the constructive characterization as well as the efficient recognition of all such graphs that are triangle-free. Furthermore, we characterize---in terms of forbidden induced subgraphs---the graphs $G$ that satisfy $h(G')=g(G')$ for every induced subgraph $G'$ of $G$.