Orientable convexity, geodetic and hull numbers in graphs

Simple item page
dc.creatorFarrugia, Alastair
dc.date2003-06-25
dc.date.accessioned2026-07-07T04:59:11Z
dc.date.available2026-07-07T04:59:11Z
dc.descriptionWe 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.
dc.description8 pages, 1 figure; submitted to European Journal of Combinatorics
dc.identifierhttps://arxiv.org/abs/math/0306367
dc.identifierhttp://arxiv.org/abs/math/0306367
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/67882
dc.subjectCombinatorics
dc.subject05C20, 05C38
dc.titleOrientable convexity, geodetic and hull numbers in graphs
dc.typetext

Files

Collections

arXiv