For every pair of vertices $u,v$ in an oriented graph, a $u$-$v$
$geodesic$ is a shortest directed path from $u$ to $v$. For an
oriented graph $D$, let $I_{D}[u,v]$ denoted the set of all
vertices lying on a $u$-$v$ geodesic or a $v$-$u$ geodesic. And
for $Ssubseteq V(D)$, let $I_{D}[S]$ denoted the union of all
$I_{D}[u,v]$ for all $u,vin S$. If $S$ is a $convex$ set then
$I_{D}[S]=S$. Let $[S]_{D}$ denoted the smallest convex set
containing $S$. The $geodetic$ $number$ $g(D)$ of an oriented
graph $D$ is the minimum cardinality of a set $S$ with
$I_{D}[S]=V(D)$. The $hull$ $number$ $h(D)$ of an oriented graph
$D$ is the minimum cardinality of a set $S$ with $[S]_{D}=V(D)$.
For a connected graph $G$, let $g^{-}(G)=$min${g(D)$:$D$ is an
orientation of $G$ $}$ and $g^{+}(G)=$max${g(D)$:$D$ is an
orientation of $G$ $}$. And let $h^{-}(G)=$min${h(D)$:$D$ is an
orientation of $G$ $}$ and $h^{+}(G)=$max${h(D)$:$D$ is an
orientation of $G$ $}$. We show that $h^{+}(G)>h^{-}(G)$ and
$g^{+}(G)>g^{-}(G)$ for every connected graph $G$ with
$|V(G)|geq 3$. Then we show that $h^{+}(G)=h^{-}(G)+1$ if and
only if $G$ is isomorphic to $K_{3}$ or $K_{1,r}$ for $rgeq 2$
and prove that for every connected graph $G$, $h^{+}(G)geq 5$ if
and only if $|V(G)|geq 5$ and $G
cong C_{5}$. Let
$Sh^{*}(G)={h(D)$:$D$ is a strongly connected orientation of $G$
$}$ and we have $Sh^{*}(K_{n})={2}$. Let a graph $C(n,t)$ with
$V(C(n,t))={1,2,...,n,x,y}$ and
$E(C(n,t))={i(i+1):i=1,2,...,n-1}cup {1n}cup {1x}cup
{ty}$. We also have $h^{-} (C(n,t))<g^{-}(C(n,t))<h^{+}(C(n,t))
=g^{+}(C(n,t))$ if $n geq 5$, $t
eq frac{n}{2}$ and $3leq
tleq n-1$. The last result answers a problem of Farrugia in [7].
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0623106-173155 |
| Date | 23 June 2006 |
| Creators | Hung, Jung-Ting |
| Contributors | none, none, none, none, Li-Da Tong |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0623106-173155 |
| Rights | off_campus_withheld, Copyright information available at source archive |
Page generated in 0.0023 seconds