Mathematics – Combinatorics
Scientific paper
2003-06-25
Mathematics
Combinatorics
8 pages, 1 figure; submitted to European Journal of Combinatorics
Scientific paper
We prove three results conjectured or stated by Chartrand, Fink and Zhang [European J. Combin {\bf 21} (2000) 181--189, Disc. Appl. Math. {\bf 116} (2002) 115--126, and pre-print of ``The hull number of an oriented graph'']. For a digraph $D$, Chartrand et al. defined the geodetic, hull and convexity number -- $g(D)$, $h(D)$ and $con(D)$, respectively. For an undirected graph $G$, $g^{-}(G)$ and $g^{+}(G)$ are the minimum and maximum geodetic numbers over all orientations of $G$, and similarly for $h^{-}(G)$, $h^{+}(G)$, $con^{-}(G)$ and $con^{+}(G)$. Chartrand and Zhang gave a proof that $g^{-}(G) < g^{+}(G)$ for any connected graph with at least three vertices. We plug a gap in their proof, allowing us also to establish their conjecture that $h^{-}(G) < h^{+}(G)$. If $v$ is an end-vertex, then in any orientation of $G$, $v$ is either a source or a sink. It is easy to see that graphs without end-vertices can be oriented to have no source or sink; we show that, in fact, we can avoid all extreme vertices. This proves another conjecture of Chartrand et al., that $con^{-}(G) < con^{+}(G)$ iff $G$ has no end-vertices.
Farrugia Alastair
No associations
LandOfFree
Orientable convexity, geodetic and hull numbers in graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Orientable convexity, geodetic and hull numbers in graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Orientable convexity, geodetic and hull numbers in graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-68289