<p>Let <i>G</i> be a graph on <i>n</i> vertices and <i>S</i> a subset of vertices of <i>G</i>; the boundary of <i>S</i> is the set, <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_769_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="25" /> </InlineMediaObject> <EquationSource Format="TEX">\(\partial S\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>∂</mi> <mi>S</mi> </mrow> </math></EquationSource> </InlineEquation>, of edges of <i>G</i> connecting <i>S</i> to its complement in <i>G</i>. The isoperimetric number of <i>G</i> is the minimum of <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_769_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="72" /> </InlineMediaObject> <EquationSource Format="TEX">\(\left| \partial S \right| /\left| S \right| \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mfenced close="|" open="|"> <mi>∂</mi> <mi>S</mi> </mfenced> <mo stretchy="false">/</mo> <mfenced close="|" open="|"> <mi>S</mi> </mfenced> </mrow> </math></EquationSource> </InlineEquation> overall <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_769_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="75" /> </InlineMediaObject> <EquationSource Format="TEX">\(S \subset V(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>S</mi> <mo>⊂</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> of at most <i>n</i>/2 vertices. Let <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_769_Article_IEq4.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="46" /> </InlineMediaObject> <EquationSource Format="TEX">\(k \le n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≤</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation> be positive integers. The Johnson graph is the graph, <i>J</i>(<i>n</i>,&#xa0;<i>k</i>), whose vertices are all the subsets of size <i>k</i> of <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_769_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="79" /> </InlineMediaObject> <EquationSource Format="TEX">\(\{1,\dots ,n\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <mi>n</mi> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>, two of which are adjacent if their intersection has cardinality equal to <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_769_Article_IEq6.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">\(k-1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>. In this paper, we show that the asymptotic value of the isoperimetric number of the Johnson graph <i>J</i>(<i>n</i>,&#xa0;2) is equal to <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_769_Article_IEq7.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="77" /> </InlineMediaObject> <EquationSource Format="TEX">\( (2-\sqrt{2})n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mn>2</mn> <mo>-</mo> <msqrt> <mn>2</mn> </msqrt> <mo stretchy="false">)</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A note on the asymptotic value of the isoperimetric number of J(n, 2)

  • Ruy Fabila-Monroy,
  • Daniel Gregorio-Longino

摘要

Let G be a graph on n vertices and S a subset of vertices of G; the boundary of S is the set, \(\partial S\) S , of edges of G connecting S to its complement in G. The isoperimetric number of G is the minimum of \(\left| \partial S \right| /\left| S \right| \) S / S overall \(S \subset V(G)\) S V ( G ) of at most n/2 vertices. Let \(k \le n\) k n be positive integers. The Johnson graph is the graph, J(nk), whose vertices are all the subsets of size k of \(\{1,\dots ,n\}\) { 1 , , n } , two of which are adjacent if their intersection has cardinality equal to \(k-1\) 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-\sqrt{2})n\) ( 2 - 2 ) n .