Orientable convexity, geodetic and hull numbers in graphs

DOI10.1016/J.DAM.2005.03.002zbMATH Open1066.05061arXivmath/0306367OpenAlexW2096146759MaRDI QIDQ2486069FDOQ2486069

Authors: Alastair Farrugia 

Publication date: 5 August 2005

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

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.

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

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

zbMATH Keywords

ConvexGeodesicOriented graphHull numberTransitively orientable

Mathematics Subject Classification ID

Distance in graphs (05C12)

Cites Work

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

Cited In (12)

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)

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)