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.

Zitieren

Zitierform:

Dourado, Mitre C. / Protti, Fábio / Rautenbach, Dieter / et al: On the hull number of triangle-free graphs. 2009.

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export