×

Hull numbers of path convexities on graphs. (English) Zbl 1166.05018

Changat, Manoj (ed.) et al., Convexity in discrete structures. Joint proceedings of the international instructional workshop on convexity in discrete structures, Thiruvananthapuram, Kerala, India, March 22–April 2, 2006 and the international workshop on metric and convex graph theory, Barcelona, Spain, June 12–16, 2006. Mysore: Ramanujan Mathematical Society (ISBN 978-81-902545-5-7/hbk). Ramanujan Mathematical Society Lecture Notes Series 5, 11-23 (2008).
Summary: A feasible family of paths in a connected graph \(G\) such as the ‘induced paths’, ‘triangle paths’ and ‘all paths’ defines a convexity on \(G\). We survey the behavior of such convexities on the hull number and rank. Along this, we present algorithms for computing the hull number, hull set and the convex hull for the induced path convexity using the decomposition algorithms by clique separators.
For the entire collection see [Zbl 1143.05001].

MSC:

05C99 Graph theory
05C12 Distance in graphs
05C38 Paths and cycles
05C75 Structural characterization of families of graphs
52A01 Axiomatic and generalized convexity
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite