On the Hull Number of Triangle-Free Graphs

Abstract

A set of vertices C in a graph is convex if it contains all vertices which lie on shortest paths between vertices in C. The convex hull of a set of vertices S is the smallest convex set containing S. The hull number $h(G)$ of a graph G is the smallest cardinality of a set of vertices whose convex hull is the vertex set of G. For a connected triangle-free graph G of order n and diameter d at least 4, we prove that $h(G)\leq(n-d+3)/3$ if G has minimum degree at least 3 and that $h(G)\leq2(n-d+5)/7$, if G is cubic. Furthermore for a connected graph G of order n, girth g at least 5, minimum degree at least 2, and diameter d, we prove $h(G)\leq2+(n-d-1)/\left\lceil\frac{g-1}{2}\right\rceil$. All bounds are best possible.