2023/12/05 by Ruy Fabila‐Monroy, Fabila-Monroy, Ruy, Daniel Gregorio-Longino +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2312.03114
openalex publication_date 2023/12/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a graph on n vertices and S a subset of vertices of G; the boundary of S is the set, ∂ S, of edges of G connecting S to its complement in G. The isoperimetric number of G, is the minimum of | ∂ S |/| S | overall S ⊂ V(G) of at most n/2 vertices. Let k ≤ n be positive integers. The Johnson graph is the graph, J(n,k), whose vertices are all the subsets of size k of \1,…,n\, two of which are adjacent if their intersection has cardinality equal to k-1. In this paper we show that the asymptotic value of the isoperimetric number of the Johnson graph J(n,2) is equal to (2-√(2))n.