IJPAM: Volume 80, No. 3 (2012)

THE UPPER HULL NUMBER OF A GRAPH

J. John$^1$, V. Mary Gleeta$^2$
$^1$Department of Mathematics
Government College of Engineering
Tirunelveli, 627 007, INDIA
$^2$Department of Mathematics
Cape Institute of Technology
Levengipuram, 627114, INDIA


Abstract. For a connected graph $G = (V, E)$, the hull number $h(G)$ of a graph $G$ is the minimum cardinality of a set of vertices whose convex hull contains all vertices of $G$. A hull set $S$ in a connected graph $G$ is called a minimal hull set of $G$ if no proper subset of $S$ is a hull set of $G$. The upper hull number $h^+(G)$ of $G$ is the maximum cardinality of a minimal hull set of $G$. Connected graphs of order $p$ with upper hull number $p$ or $p-1$ are characterized. It is shown that for every integer $a \geq 2$, there exists a connected graph $G$ with $h(G)=a$ and $h^+(G)=2a$. A graph $G$ is an extreme hull graph if $h(G) = ex(G)$, that is if $G$ has a unique minimum hull set consisting of the extreme vertices of $G$. It is shown that for every pair $a$, $b$ of integers with $2 \leq a \leq b$, there exists a connected extreme hull graph $G$ such that $h(G) = a = ex(G)$ and $g(G) = b$, where $g(G)$ is the geodetic number of a graph.

Received: March 11, 2012

AMS Subject Classification: 05C12

Key Words and Phrases: hull number, upper hull number, geodetic number

Download paper from here.


Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2012
Volume: 80
Issue: 3