Smoothness in weakly modular graphs identified by forbidden subgraphs
Smooth weakly modular graphs
Discrete Mathematics
Summary
This paper studies special properties called smoothness and strong smoothness in graphs, where certain groups of points behave nicely with distances. The authors focus on a big class of graphs important in metric graph theory and find exact small patterns that cannot appear if these properties hold. They also identify graphs that are building blocks for strongly smooth graphs, helping understand their structure better. These results solve a previously open problem in the area.
What this means in practice
- •For network designers: Exclude certain network patterns that prevent optimal routing by identifying forbidden subgraphs related to smoothness.
- •For database engineers: Improve data structure design by understanding graph convexity properties that affect query optimization in metric spaces.
A theory result. No direct application yet.
Authors
Victor Chepoi, Bruno J. Schmidt, Peter F. Stadler
Abstract
A graph $G=(V,E)$ is called smooth (respectively, strongly smooth) if for any two vertices $u,v\in V$, the distance point-shadow $v|u := \{ x\in V: d(u,x)=d(u,v)+d(v,x)\}$, respectively, the point-shadow $v/u := \{ x\in V: v\in\mathrm{conv}(u,x)\}$, is geodesically convex. Smooth graphs have been introduced by Nebeský (2005) in the context of step systems. Graphs with convex point-shadows and convex distance point-shadows also naturally occur in convexity theory. Brešar et al. (2026) recently showed that several classes of graphs are smooth and that smoothness is preserved by Cartesian products, gated amalgams, and isometric subgraphs. Weakly modular graphs comprise the most important classes of graphs from Metric Graph Theory: median, modular, Helly, bridged, and dual polar graphs. In this note, we characterize smooth and strongly smooth weakly modular graphs in terms of forbidden isometric subgraphs on 5 and 7 vertices. This settles Problem 1 of the paper by Brešar et al. We also characterize prime strongly smooth weakly modular graphs, i.e., strongly smooth weakly modular graphs that cannot be obtained from smaller graphs by Cartesian products and gated amalgams.