Peakless functions on graphs (Q678883)

A real-valued function on the vertices \(V\) of a graph is peakless iff on each shortest path it reaches its maximum at one of the endpoints. A geodesic is a vertex path each subpath of 3 vertices of which is a shortest one. A subset of \(V\) is totally convex (tc) if it contains any geodesic between two of its elements. It is shown that these are exactly the level sets of peakless functions. A graph is peakless-prime if no proper tc-subsets exist. Any graph admits a decomposition into peakless-prime subsets which is simultaneously modular and simplicial. This decomposition may be constructed in polynomial time.