Peakless functions on graphs
type: Item
instance of: scholarly article
title: Peakless functions on graphs
zbMATH Open document ID: 0871.05051
DOI: 10.1016/S0166-218X(96)00007-8
author: Victor Chepoi
published in: Discrete Applied Mathematics
publication date: 1997-09-09T00:00:00Z
full work available at URL: dam
review text: 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.
reviewed by: Frank Plastria
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1004437
zbMATH Keywords: graphs
zbMATH Keywords: geodesics
zbMATH Keywords: peakless functions
zbMATH Keywords: prime subgraph decomposition linear differential equation
zbMATH Keywords: singular oscillators
MaRDI profile type: Publication
cites work: A characterisation of rigid circuit graphs
cites work: Q5719717
cites work: Peakless and monotone functions on G-spaces
cites work: Convex Location Problems on Tree Networks
cites work: Simplicial decompositions of graphs: A survey of applications
cites work: Q3999150
cites work: Simplicial tree-decompositions of infinite graphs. III: The uniqueness of prime decompositions
cites work: A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger
cites work: Convexity in Graphs and Hypergraphs
cites work: Über simpliziale Zerfällungen beliebiger (endlicher oder unendlicher) Graphen
cites work: Q3929755
cites work: A characterization of ptolemaic graphs
cites work: A classification of Busemann G-surfaces which possess convex functions
cites work: P-Components and the Homogeneous Decomposition of Graphs
cites work: Q3940405
cites work: Q3686754
cites work: Q3683903
cites work: Incremental modular decomposition
cites work: Some aspects of perfect elimination orderings in chordal graphs
cites work: Q3943574
cites work: Q5185609
cites work: Q4741327
cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
cites work: Q3141898
description: scientific article; zbMATH DE number 1004437