Peakless functions on graphs

DOI10.1016/S0166-218X(96)00007-8MaRDI QIDQ678883zbMATH OpenFDO

Authors Victor Chepoi

Publication date 9 September 1997

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

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

geodesicsgraphspeakless functionsprime subgraph decomposition linear differential equationsingular oscillators

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (05C99)

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.

Recommendations

• Counting peaks on graphs
• Totally flat foliations and peakless functions
• scientific article; zbMATH DE number 4133841
• Function Decomposition in Main and Lesser Peaks
• A geometric study of the split decomposition

Cites work

• A characterisation of rigid circuit graphs
• A characterization of ptolemaic graphs
• A classification of Busemann G-surfaces which possess convex functions
• A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger
• Convex Location Problems on Tree Networks
• Convexity in Graphs and Hypergraphs
• scientific article; zbMATH DE number 439012 (Why is no real title available?)
• scientific article; zbMATH DE number 3906240 (Why is no real title available?)
• scientific article; zbMATH DE number 3908482 (Why is no real title available?)
• scientific article; zbMATH DE number 3743278 (Why is no real title available?)
• scientific article; zbMATH DE number 3757213 (Why is no real title available?)
• scientific article; zbMATH DE number 3760908 (Why is no real title available?)
• scientific article; zbMATH DE number 48089 (Why is no real title available?)
• scientific article; zbMATH DE number 3794868 (Why is no real title available?)
• scientific article; zbMATH DE number 3892077 (Why is no real title available?)
• scientific article; zbMATH DE number 3182580 (Why is no real title available?)
• Incremental modular decomposition
• P-Components and the Homogeneous Decomposition of Graphs
• Peakless and monotone functions on G-spaces
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Simplicial decompositions of graphs: A survey of applications
• Simplicial tree-decompositions of infinite graphs. III: The uniqueness of prime decompositions
• Some aspects of perfect elimination orderings in chordal graphs
• Über simpliziale Zerfällungen beliebiger (endlicher oder unendlicher) Graphen

Cited in

(3)

• Representing a Functional Curve by Curves with Fewer Peaks
• scientific article; zbMATH DE number 937018 (Why is no real title available?)
• Totally flat foliations and peakless functions

This page was built for publication: Peakless functions on graphs

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