Orientable convexity, geodetic and hull numbers in graphs

DOI10.1016/J.DAM.2005.03.002MaRDI QIDQ2486069zbMATH OpenOpenAlexFDO

Authors Alastair Farrugia

Publication date 5 August 2005

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0306367

zbMATH Keywords

ConvexGeodesicOriented graphHull numberTransitively orientable

Mathematics Subject Classification ID

Distance in graphs (05C12)

Abstract: We prove three results conjectured or stated by Chartrand, Fink and Zhang [European J. Combin {�f 21} (2000) 181--189, Disc. Appl. Math. {�f 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)$, $co{n}^{-}(G)$ and $co{n}^{+}(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 $co{n}^{-}(G)<co{n}^{+}(G)$ iff $G$ has no end-vertices.

Recommendations

• The hull and geodetic numbers of orientations of graphs
• Hull and geodetic numbers for some classes of oriented graphs
• Hull and geodetic numbers for some classes of oriented graphs
• Convexity, geodetic, and hull numbers of the join of graphs
• Convexity in oriented graphs
• Convex and linear orientations of polytopal graphs
• scientific article; zbMATH DE number 5531985
• scientific article; zbMATH DE number 2076940
• scientific article; zbMATH DE number 2076931
• On the Steiner, geodetic and hull numbers of graphs

Cites work

• Convexity in oriented graphs
• The geodetic number of an oriented graph
• The hull number of an oriented graph

Cited in

(12)

• scientific article; zbMATH DE number 5531985 (Why is no real title available?)
• The orientable numbers of a graph
• Hull and geodetic numbers for some classes of oriented graphs
• Hull and geodetic numbers for some classes of oriented graphs
• Independent domination versus packing in subcubic graphs
• On the Carathéodory and exchange numbers of geodetic convexity in graphs
• Strong geodetic problem in networks
• The hull and geodetic numbers of orientations of graphs
• On the in-neighbor convexity
• Convexity in oriented graphs
• The convexity spectra of graphs
• scientific article; zbMATH DE number 2076940 (Why is no real title available?)

This page was built for publication: Orientable convexity, geodetic and hull numbers in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2486069)