Discrete isoperimetric inequalities on the strong products of paths

2025/02/16 by Runze Wang, Wang, Runze
Mathematics · #05C35 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Point processes and geometric inequalities #advanced mathematical theories

paper · pdf · doi:10.48550/arxiv.2502.12199

openalex publication_date 2025/02/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For a graph G=(V, E) and a nonempty set S⊆ V, the vertex boundary of S, denoted by ∂_G(S), is defined to be the set of vertices that are not in S but have at least one neighbor in S. In this paper, for G being a strong product of two paths, we determine the cases in which |∂_G(S)| is minimized.

Related

• The Boundary of a Graph and its Isoperimetric Inequality
• Edge-isoperimetric inequalities for the symmetric product of graphs
• Sharp discrete isoperimetric inequalities in periodic graphs via discrete PDE and Semidiscrete Optimal Transport
• Vertex Isoperimetric Inequalities for a Family of Graphs on Z^k
• Isoperimetry in product graphs