On the hull number of triangle-free graphs

Dourado, Mitre C.; Protti, Fábio; Rautenbach, Dieter GND; Szwarcfiter, Jayme Luiz

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\geq 3, we prove that h(G)\leq (n-d+3)/3, if G has minimum degree at least 3 and that h(G)\leq 2(n-d+5)/7, if G is cubic. Furthermore, for a connected graph G of order n, girth g\geq 4, minimum degree at least 2, and diameter d, we prove h(G)\leq 2+ (n-d-1)/\left\lceil\frac{g-1}{2}\right \rceil. All bounds are best possible.


Citation style:
Could not load citation form.


Use and reproduction:
All rights reserved