Loading...
Loading...

Go to the content (press return)

On a problem by Shapozenko on Johnson Graphs

Author
Diego , V.; Serra, O.
Type of activity
Journal article
Journal
Graphs and combinatorics
Date of publication
2018-09
Volume
34
Number
5
First page
947
Last page
964
DOI
https://doi.org/10.1007/s00373-018-1923-7 Open in new window
Repository
http://hdl.handle.net/2117/123217 Open in new window
URL
https://link.springer.com/article/10.1007%2Fs00373-018-1923-7 Open in new window
Abstract
The Johnson graph J(n, m) has the m-subsets of {1,2,…,n} as vertices and two subsets are adjacent in the graph if they share m-1 elements. Shapozenko asked about the isoperimetric function µn,m(k) of Johnson graphs, that is, the cardinality of the smallest boundary of sets with k vertices in J(n, m) for each 1=k=(nm) . We give an upper bound for µn,m(k) and show that, for each given k such that the solution to the Shadow Minimization Problem in the Boolean lattice is unique, and each suffici...
Citation
Diego , V., Serra, O. On a problem by Shapozenko on Johnson Graphs. "Graphs and combinatorics", Setembre 2018, vol. 34, núm. 5, p. 947-964.
Keywords
Isoperimetric problem, Johnson graph, Shift compression
Group of research
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants

Attachments