Cheeger Constant

Author

Eric W. Weisstein
March 25, 2026

This notebook downloaded from https://mathworld.wolfram.com/notebooks/GraphTheory/CheegerConstant.nb.

For more information, see Eric's MathWorld entry https://mathworld.wolfram.com/CheegerConstant.html.

©2026 Wolfram Research, Inc. except for portions noted otherwise

Sources

Wikipedia

https://en.wikipedia.org/wiki/Cheeger_constant_(graph_theory)

Properties

0

Cheeger constant h(G): every disconnected graph on >1 vertices has h(G) = 0

GraphDataCountTable

table=GraphDataCountTable["CheegerConstant"]

DateString[]

TextGrid[OEISUpdates[table],Dividers->All]

Parametrized families

<<MathWorld`Graphs`

Alkane

Inferred for n > 6:

seq=Table[GraphData[{"Alkane",n},"CheegerConstant"],{n,10}]

FullSimplify[FindSequenceFunction[DeleteMissing@seq,n],n∈Integers]

FullSimplify[((1-3 (((-1))^n)+6 n)/(-2+3 n+9 (n^2)))-(1/(3Floor[(n/2)]+1)),n∈Integers&&n>0]

Table[((1-3 (((-1))^n)+6 n)/(-2+3 n+9 (n^2)))-(1/(3Floor[(n/2)]+1)),{n,10}]

FindGeneratingFunction[DeleteMissing@seq,x,ValidationLength->2]//Head//Timing

Table[(1/(3Floor[(n/2)]+1)),{n,10}]

AlternatingGroupGraph

seq=Table[GraphData[{"AlternatingGroupGraph",n},"CheegerConstant"],{n,2,6}]

Andrasfai

Inferred for n > 7:

seq=Table[GraphData[{"Andrasfai",n},"CheegerConstant"],{n,20}]

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

FindGeneratingFunction[seq,x,ValidationLength->2]//Head//Timing

Table[Piecewise[{{n^2/(3 n-2),Mod[n,2]==0},{(n^2+(-1)^((n-1)/2))/(3 n-1),Mod[n,2]==1}}],{n,20}]

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"CheegerConstant"],{n,20}]

Antiprism

Entity["Graph",{"Antiprism",n}]["CheegerConstant"]

seq=Table[GraphData[{"Antiprism",n},"CheegerConstant"],{n,3,25}]

FindSequenceFunction[DeleteMissing@seq,n-2]

Apollonian

Inferred for n > 3:

seq=Table[GraphData[{"Apollonian",n},"CheegerConstant"],{n,6}]

Table[Piecewise[{{2,n==1},{7/3,n==2},{7/4,n==3}},(13 2^(n-3)+1)/(20 3^(n-4)+1)],{n,6}]

Barbell

seq=Table[GraphData[{"Barbell",n},"CheegerConstant"],{n,3,20}]

FindSequenceFunction[DeleteMissing@seq,n-2]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"CheegerConstant"],{n,20}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"CheegerConstant"],{n,20}]

Book

seq=Table[GraphData[{"Book",n},"CheegerConstant"],{n,20}]

Bruhat

seq=Table[GraphData[{"Bruhat",n},"CheegerConstant"],{n,6}]

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"CheegerConstant"],{n,20}]

Cameron

seq=Table[GraphData[{"Cameron",n},"CheegerConstant"],{n,20}]

Centipede

seq=Table[GraphData[{"Centipede",n},"CheegerConstant"],{n,10}]

Table[Piecewise[{{1,n==1}},(1/(2Floor[(n/2)]))],{n,10}]

FindSequenceFunction[DeleteMissing@seq,n]

CocktailParty

seq=Table[GraphData[{"CocktailParty",n},"CheegerConstant"],{n,20}]

FindSequenceFunction[DeleteMissing@seq,n]

Complete

Entity["Graph",{"Complete",n}]["CheegerConstant"]

seq=Table[GraphData[{"Complete",n},"CheegerConstant"],{n,30}]

FullSimplify[FindSequenceFunction[DeleteMissing@Drop[seq,1],n-1],n∈Integers]

Table[Piecewise[{{Missing["NotApplicable"],n==1}},(1/4) (1-(((-1))^n)+2 n)],{n,30}]

Table[Piecewise[{{Missing["NotApplicable"],n==1}},Ceiling[(n/2)]],{n,30}]

because for |A| = k, |\partial A| = k(n-k), so |\partial A|/|A| = n-k, minimized at k = floor(n/2).

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["CheegerConstant"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"CheegerConstant"],{n,20}]

FullSimplify[FindSequenceFunction[DeleteMissing@seq,n],n∈Integers]

FullSimplify[Piecewise[{{((m n)/(m+n)),Mod[m,2]==0&&Mod[n,2]==0},{((m n+1)/(m+n)),Mod[m n,2]==1},{((m n)/(m+n-1)),Mod[m+n,2]==1}}]/.m->n,n∈Integers]

Table[Piecewise[{{n/2, Mod[n, 2] == 0}, {(1 + n^2)/(2*n), Mod[n, 2] == 1}}],{n,20}]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["CheegerConstant"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"CheegerConstant"],
Piecewise[{{((m n)/(m+n)),Mod[m,2]==0&&Mod[n,2]==0},{((m n+1)/(m+n)),Mod[m n,2]==1},{((m n)/(m+n-1)),Mod[m+n,2]==1}}]
},{n,10},{m,n}],1],{_,x_,x_}]

if A contains a vertices from one side and b from the other, then
  |\partial A| = a(n-b) + b(m-a).
  Minimizing gives
  h(K_{m,n}) =
  mn/(m+n)       if m,n are both even,
  (mn+1)/(m+n)   if m,n are both odd,
  mn/(m+n-1)     if m+n is odd.

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["CheegerConstant"]

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"CheegerConstant"],{n,10}]

FullSimplify[((Ceiling[(k m+k n+m n)/2])/(Floor[(k+m+n)/2]))/.{k->n,m->n}]

seq=Table[((Ceiling[((3 (n^2))/2)])/(Floor[((3 n)/2)])),{n,20}]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers]

FullSimplify[-((-1+n-6 (n^2)+(((-1))^n) (1+n))/(-2+6 n)),Mod[n,2]==#]&/@{0,1}

Table[Piecewise[{{n,Mod[n,2]==0},{((3 (n^2)+1)/(3 n-1)),Mod[n,2]==1}}],{n,20}]

gf=x FindGeneratingFunction[seq,x]//FullSimplify

FullSimplify[SeriesCoefficient[gf,{x,0,n}],n∈Integers]

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["CheegerConstant"]

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"CheegerConstant"],
((Ceiling[(k m+k n+m n)/2])/(Floor[(k+m+n)/2]))
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

Yes. If you mean the Wikipedia version

h(G) = min { |\partial A|/|A| : A subseteq V(G), 0 < |A| <= |V(G)|/2 },

and K_{k,m,n} is the complete tripartite graph with part sizes k,m,n, then

h(K_{k,m,n}) = Ceiling[(km + kn + mn)/2]/Floor[(k + m + n)/2].

Here km + kn + mn is just the number of edges of K_{k,m,n}. The notation K_{k,m,n} for the complete tripartite graph and the Wikipedia Cheeger definition are standard. ([MathWorld][1])

A convenient way to see this is:

If A contains x,y,z vertices from the three parts, with
s = x + y + z <= (k + m + n)/2,
then the boundary size is

|\partial A|
= x(m + n - y - z) + y(k + n - x - z) + z(k + m - x - y).

For fixed s, this quadratic is minimized when x,y,z are as balanced as possible relative to the part sizes, and the overall minimum occurs at the largest allowed s, namely s = Floor[(k + m + n)/2]. Taking x,y,z as close as possible to k/2,m/2,n/2 then gives the minimum cut size

min |\partial A| = Ceiling[(km + kn + mn)/2],

so dividing by s = Floor[(k + m + n)/2] gives the formula above.

Checks:

* K_{1,1,1} (triangle): h = Ceiling[3/2]/1 = 2.
* K_{1,1,2} (diamond): h = Ceiling[5/2]/2 = 3/2.
* K_{2,2,2} (octahedral graph): h = Ceiling[12/2]/3 = 2.
* If one part is 0, this reduces to the bipartite case
  h(K_{m,n}) = Ceiling[mn/2]/Floor[(m+n)/2].

If you want, I can also write this as a short WL function `CheegerConstant[CompleteTripartiteGraph[{k,m,n}]]` or give the analogous closed form for conductance.

[1]: https://mathworld.wolfram.com/CompleteTripartiteGraph.html "Complete Tripartite Graph -- from Wolfram MathWorld"

CompleteTripartiteMinusPerfectMatching

seq=Table[GraphData[{"CompleteTripartiteMinusPerfectMatching",{2n,2n,2n}},"CheegerConstant"],{n,10}]

FindSequenceFunction[seq,n]

Assuming you mean

[
G = K_{2n,2n,2n} - M
]

where (M) is any perfect matching, the exact Cheeger constant is

[
\boxed{h(G) = 2n - 1.}
]

Since (G) is ((4n-1))-regular, the conductance is therefore

[
\boxed{\phi(G) = \frac{2n-1}{4n-1}.}
]

A perfect matching meets every vertex exactly once, so here it has (3n) edges. Under the usual edge-boundary normalization, conductance for a (d)-regular graph is (h(G)/d). ([MathWorld][1])

Proof: write the three parts as (A,B,C), each of size (2n).

Let (x_{AB}, x_{AC}, x_{BC}) be the numbers of matching edges of (M) between the corresponding parts. Since every vertex of (A) is matched once, and similarly for (B,C),

[
x_{AB}+x_{AC}=2n,\qquad
x_{AB}+x_{BC}=2n,\qquad
x_{AC}+x_{BC}=2n,
]

so

[
x_{AB}=x_{AC}=x_{BC}=n.
]

Now let (S \subseteq V(G)) with (|S|=s \le 3n), and set

[
a=|S\cap A|,\qquad b=|S\cap B|,\qquad c=|S\cap C|,
\qquad a+b+c=s.
]

First compute the cut in the full complete tripartite graph (K_{2n,2n,2n}). The number of crossing edges is

[
\delta_K(S)
= a((2n-b)+(2n-c))

* b((2n-a)+(2n-c))
* c((2n-a)+(2n-b)),
  ]

hence

[
\delta_K(S)=4ns-2(ab+ac+bc).
]

Since

[
(a-b)^2+(b-c)^2+(c-a)^2 \ge 0,
]

we have

[
ab+ac+bc \le \frac{s^2}{3}.
]

Therefore

[
\delta_K(S) \ge 4ns-\frac{2s^2}{3}.
]

Now pass from (K_{2n,2n,2n}) to (G) by deleting the matching (M). Let (m_{\times}(S)) be the number of deleted matching edges crossing the cut. Because (M) is a matching and (s \le 3n), at most (s) deleted edges can cross, so

[
m_{\times}(S)\le s.
]

Thus

[
\delta_G(S)=\delta_K(S)-m_{\times}(S)
\ge 4ns-\frac{2s^2}{3}-s
= s\left(4n-1-\frac{2s}{3}\right).
]

Since (s\le 3n),

[
4n-1-\frac{2s}{3} \ge 4n-1-2n = 2n-1,
]

so for every (S) with (|S|\le 3n),

[
\frac{\delta_G(S)}{|S|} \ge 2n-1.
]

Hence

[
h(G)\ge 2n-1.
]

For the matching upper bound, choose (S) as follows:

[
S =
{\text{vertices of }A\text{ matched by }M\text{ to }B}
;\cup;
{\text{vertices of }B\text{ matched by }M\text{ to }C}
;\cup;
{\text{vertices of }C\text{ matched by }M\text{ to }A}.
]

Each of those three sets has size (n), so (|S|=3n), and (a=b=c=n). Also, every deleted matching edge has exactly one endpoint in (S), so (m_{\times}(S)=3n).

Therefore

[
\delta_K(S)=4n(3n)-2(n^2+n^2+n^2)=12n^2-6n^2=6n^2,
]

and hence

[
\delta_G(S)=6n^2-3n=3n(2n-1).
]

So

[
\frac{\delta_G(S)}{|S|}
=======================

# \frac{3n(2n-1)}{3n}

2n-1,
]

which gives

[
h(G)\le 2n-1.
]

Combining both bounds,

[
\boxed{h!\left(K_{2n,2n,2n}-\text{perfect matching}\right)=2n-1.}
]

And since every vertex loses exactly one edge from (K_{2n,2n,2n}), the degree is

[
(2n+2n)-1 = 4n-1,
]

so

[
\boxed{\phi!\left(K_{2n,2n,2n}-\text{perfect matching}\right)
= \frac{2n-1}{4n-1}.}
]

WL forms:

```wl
2 n - 1
```

```wl
(2 n - 1)/(4 n - 1)
```

[1]: https://mathworld.wolfram.com/PerfectMatching.html?utm_source=chatgpt.com "Perfect Matching -- from Wolfram MathWorld"

CossidentePenttila

GraphData["CossidentePenttila","CheegerConstant"]

CrossedPrism

Inferred for n > 5:

seq=Table[GraphData[{"CrossedPrism",2n},"CheegerConstant"],{n,2,12}]

Table[1/Floor[n/2],{n,2,12}]

Crown

Inferred for n > 10:

seq=Table[GraphData[{"Crown",n},"CheegerConstant"],{n,20}]

FullSimplify[Refine[ExpandAll@FindSequenceFunction[DeleteMissing@seq,n],n>0],n∈Integers]

Table[((1-(((-1))^n)+2 (-2+n) n)/(4 n)),{n,20}]

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["CheegerConstant"]

seq=Table[GraphData[{"CubeConnectedCycle",n},"CheegerConstant"],{n,3,8}]

Possibly 1/n?

Cycle

Entity["Graph",{"Cycle",n}]["CheegerConstant"]

seq=Table[GraphData[{"Cycle",n},"CheegerConstant"],{n,3,30}]

Table[(2/(Floor[(n/2)])),{n,3,30}]

CycleComplement

seq=Table[GraphData[{"CycleComplement",n},"CheegerConstant"],{n,3,20}]

FullSimplify[FindSequenceFunction[DeleteMissing@seq,n-2],n∈Integers]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"CheegerConstant"],{n,3,14}]

Dipyramid

seq=Table[GraphData[{"Dipyramid",n},"CheegerConstant"],{n,3,20}]

FullSimplify[FindSequenceFunction[DeleteMissing@seq,n-2],n∈Integers]

FullSimplify[((3-(((-1))^n)+2 n)/(1+n)),Mod[n,2]==#]&/@{0,1}

DorogovtsevGoltsevMendes

seq=Table[GraphData[{"DorogovtsevGoltsevMendes",n},"CheegerConstant"],{n,0,7}]

Conjectured:

Table[((2^n)/(Floor[(1/4) ((3^n)+3)])),{n,0,7}]

I tried, but the proof attempt exposed a counterexample.

For this family, `DGM(0)=P_2`, and `DGM(n)` is obtained by adding a new vertex on every edge at each step; equivalently, `DGM(n)` can be viewed recursively as three copies of `DGM(n-1)` glued pairwise at the three older hub vertices. The graph has

[
|V(DGM(n))|=\frac{3^n+3}{2}.
]

All of that is standard for the Dorogovtsev-Goltsev-Mendes graphs. ([MathWorld][1])

The problem is that the neat guess

[
h(DGM(n))=\frac{2^n}{2^n-1}
]

is already false at (n=4).

Since
[
|V(DGM(4))|=\frac{3^4+3}{2}=42,
]
the Cheeger minimization is over subsets of size at most (21). Using the exact three-copy recursion, I found a subset (S \subseteq V(DGM(4))) with

[
|S|=21,\qquad |\partial S|=16.
]

Therefore

[
h(DGM(4)) \le \frac{16}{21},
]

and since

[
\frac{16}{21}<\frac{16}{15},
]

this disproves the formula (2^n/(2^n-1)).

So I cannot prove the earlier conjecture because it is not true.

What now looks much better is the corrected formula

```wl
2^n/Floor[(3^n + 3)/4]
```

which gives

[
1,\ 2,\ \frac43,\ \frac87,\ \frac{16}{21},\ \frac{32}{61},\ \frac{64}{183},\dots
]

and matches the exact recursive dynamic-programming computation through (n=6).

So the honest status is:

* the original formula is false;
* the first counterexample is (n=4);
* a much better conjecture is

[
h(DGM(n))=\frac{2^n}{\left\lfloor (3^n+3)/4 \right\rfloor}.
]

If you want, I can write out the recursive state-based proof framework for that corrected formula.

[1]: https://mathworld.wolfram.com/Dorogovtsev-Goltsev-MendesGraph.html "https://mathworld.wolfram.com/Dorogovtsev-Goltsev-MendesGraph.html"

Not yet.

I need to correct one important point from my earlier attempt: the Dorogovtsev-Goltsev-Mendes graph is **not** the Sierpinski gasket graph. The DGM graph is the pseudofractal scale-free web, defined recursively by adding a vertex on each edge and it is a planar 2-tree; MathWorld also notes the recursive three-copy construction. Separately, there are papers comparing the pseudofractal scale-free web with the Sierpinski gasket and explicitly treating them as different graph families that happen to have the same numbers of vertices and edges. ([MathWorld][1])

So the earlier route through Sierpinski-gasket isoperimetry does **not** prove the DGM Cheeger constant. And the gasket paper I found does not solve the full Cheeger problem anyway; it proves an edge-isoperimetric statement only for induced subgraphs isomorphic to smaller gasket graphs, not for all subsets. 

So the honest status is:

* I do **not** currently have a proof of the exact DGM Cheeger formula.
* The formula I suggested beyond your computed values should still be treated as a **conjecture**, not a theorem.
* My earlier Sierpinski-based justification was not valid for DGM.

What I can still stand behind is much narrower: your data
`1, 2, 4/3, 8/7`
is real, and the original guess `2^n/(2^n-1)` matches only those first terms; I cannot honestly claim a proof for all n.

The right way to settle it seems to be a recursive finite-state dynamic program on the three boundary vertices of each top-level copy. That should either produce a genuine inductive proof or a counterexample, but I have not finished that argument.

[1]: https://mathworld.wolfram.com/Dorogovtsev-Goltsev-MendesGraph.html "Dorogovtsev-Goltsev-Mendes Graph -- from Wolfram MathWorld"

DoubleCone

seq=Table[GraphData[{"DoubleCone",n},"CheegerConstant"],{n,3,20}]

Empty

Entity["Graph",{"Empty",n}]["CheegerConstant"]

seq=Table[GraphData[{"Empty",n},"CheegerConstant"],{n,30}]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"CheegerConstant"],{n,15}]

I can prove the upper bound cleanly, but I cannot honestly prove the matching lower bound from what I have.

So the exact formula
h(Gamma_n) = Piecewise[{{1, 1 <= n <= 3}, {(Fibonacci[n - 1] + Fibonacci[n - 3])/(Fibonacci[n - 1] + 2 Fibonacci[n - 3]), n >= 4}}]
is still a conjecture from my side, not a theorem I can justify here.

What I can prove rigorously is this:

For the Fibonacci cube Gamma_n, viewed as the graph whose vertices are the independent sets of the path P_n and whose edges are single-vertex toggles, one has |V(Gamma_n)| = F_(n+2). ([arXiv][1])

For n >= 5,
h(Gamma_n) <= (F_(n-1) + F_(n-3))/(F_(n-1) + 2 F_(n-3)).

Here is the proof.

Let
S_n = {I in Ind(P_n) : I cap {2,4} != empty}.

So S_n is the family of independent sets of P_n that contain 2 or 4.

First count |S_n|.

The sets containing 2 are counted by forcing 1,3 notin I, and then choosing an arbitrary independent set on {4,5,...,n}, which is a copy of P_(n-3). Hence
#{I : 2 in I} = F_(n-1).

The sets containing 4 but not 2 are counted by forcing 2,3,5 notin I, leaving vertex 1 free and leaving an arbitrary independent set on {6,7,...,n}, which is a copy of P_(n-5). Hence
#{I : 4 in I, 2 notin I} = 2 F_(n-3).

Therefore
|S_n| = F_(n-1) + 2 F_(n-3).

Now count the edge boundary of S_n.

If I in S_n and we toggle a vertex j notin {2,4}, then membership in {2,4} does not change, so we stay inside S_n.

If I contains both 2 and 4, then removing either one still leaves the other, so we also stay inside S_n.

Therefore an edge leaves S_n only in exactly one of the following two cases:

1. I contains 2 but not 4, and we delete 2.
2. I contains 4 but not 2, and we delete 4.

Each such I contributes exactly one boundary edge, and every boundary edge arises uniquely this way. So

|partial S_n|
= #{I : 2 in I, 4 notin I} + #{I : 4 in I, 2 notin I}.

Now
#{I : 2 in I, 4 notin I}
is counted by forcing 1,3,4 notin I, then choosing an arbitrary independent set on {5,6,...,n}, a copy of P_(n-4). Hence
#{I : 2 in I, 4 notin I} = F_(n-2).

Also, as above,
#{I : 4 in I, 2 notin I} = 2 F_(n-3).

So
|partial S_n| = F_(n-2) + 2 F_(n-3) = F_(n-1) + F_(n-3).

Thus
|partial S_n|/|S_n|
= (F_(n-1) + F_(n-3))/(F_(n-1) + 2 F_(n-3)).

It remains to check that S_n is admissible for the Cheeger minimum, i.e. that |S_n| <= |V(Gamma_n)|/2. Since |V(Gamma_n)| = F_(n+2), it is enough to show
2(F_(n-1) + 2 F_(n-3)) <= F_(n+2).

And indeed
F_(n+2) - 2(F_(n-1) + 2 F_(n-3)) = 3 F_(n-4) >= 0
for n >= 5.

Therefore
h(Gamma_n) <= (F_(n-1) + F_(n-3))/(F_(n-1) + 2 F_(n-3)),
as claimed.

For n = 4, taking
S_4 = {I subseteq {2,4}}
gives |S_4| = 4 and |partial S_4| = 3, hence h(Gamma_4) <= 3/4. The cases n = 1,2,3 give h = 1 by direct inspection.

So the rigorously proved part is:

Piecewise[{
{1, 1 <= n <= 3},
{3/4, n == 4},
{(Fibonacci[n - 1] + Fibonacci[n - 3])/(Fibonacci[n - 1] + 2 Fibonacci[n - 3]), n >= 5}
}]  as an upper bound,
with equality verified only in small cases, not proved in general.

I do not want to fake the missing lower bound. Related shadow/isoperimetric questions on Q(P_n) are explicitly singled out as difficult, and the standard hypercube methods do not adapt cleanly there. ([arXiv][1])

The clean candidate extremal family is:
"all independent sets containing 2 or 4."

That is the real content behind the formula.

[1]: https://arxiv.org/pdf/1302.6039 "https://arxiv.org/pdf/1302.6039"

Fiveleaper n×n

seq=Table[GraphData[{"Fiveleaper",{n,n}},"CheegerConstant"],{n,20}]

Flower

seq=Table[GraphData[{"Flower",n},"CheegerConstant"],{n,5,20}]

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"CheegerConstant"],{n,2,10}]

Gear

seq=Table[GraphData[{"Gear",n},"CheegerConstant"],{n,3,20}]

FullSimplify[FindSequenceFunction[DeleteMissing@seq,n-2],n∈Integers]

Table[((3 (-1+(((-1))^n))+2 n (2+n))/(4 (-1+n) n)),{n,3,20}]

Table[Piecewise[{{(n+2)/(2 n-2),Mod[n,2]==0},{(n+3)/(2 n),Mod[n,2]==1}}],{n,3,20}]

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"CheegerConstant"],{n,20}]

Goldberg

seq=Table[GraphData[{"Goldberg",n},"CheegerConstant"],{n,3,20}]

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["CheegerConstant"]

seq=Table[GraphData[{"Grid",{n,n}},"CheegerConstant"],{n,20}]

FullSimplify[Piecewise[{{Missing["NotApplicable"],m==n==1}},1/Floor[Max[m,n]/2]]/.m->n]

Table[Piecewise[{{Missing["NotApplicable"], n == 1}}, 1/Floor[n/2]], {n, 20}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["CheegerConstant"]

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"CheegerConstant"],
Piecewise[{{Missing["NotApplicable"],m==n==1}},1/Floor[Max[m,n]/2]]
},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["CheegerConstant"]

seq=Table[GraphData[{"Grid",{n,n,n}},"CheegerConstant"],{n,10}]

FullSimplify[Piecewise[{{Missing["NotApplicable"],k==1&&m==1&&n==1}},1/Floor[Max[k,m,n]/2]]/.{k->n,m->n}]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["CheegerConstant"]

Sort@DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"CheegerConstant"],
Piecewise[{{Missing["NotApplicable"],k==1&&m==1&&n==1}},1/Floor[Max[k,m,n]/2]]
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"CheegerConstant"],{n,10}]

Hanoi

Inferred for n > 2:

seq=Table[GraphData[{"Hanoi",n},"CheegerConstant"],{n,6}]

Table[2/3^(n-1),{n,6}]

Helm

Inferred for n > 9:

seq=Table[GraphData[{"Helm",n},"CheegerConstant"],{n,3,20}]

FindSequenceFunction[DeleteMissing@seq,n-2]//Head//Timing

Table[Piecewise[{{1,n==3},{(n+4)/(2 n),Mod[n,2]==0},{(n+3)/(2 n-2),Mod[n,2]==1}}],{n,3,20}]

Hypercube

Entity["Graph",{"Hypercube",n}]["CheegerConstant"]

seq=Table[GraphData[{"Hypercube",n},"CheegerConstant"],{n,0,10}]

KC

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"KC",{m,n}},"CheegerConstant"],
Piecewise[{{1,m==2&&n==3}},2/Floor[n/2]]
},{n,3,10},{m,10}],1],{_,x_,x_}]

Keller

Entity["Graph",{"Keller",n}]["CheegerConstant"]

seq=Table[GraphData[{"Keller",n},"CheegerConstant"],{n,5}]

King n×n

seq=Table[GraphData[{"King",{n,n}},"CheegerConstant"],{n,20}]

Table[Piecewise[{{Missing["NotApplicable"],n==1},{2 (3 n-2)/n^2,Mod[n,2]==0},{2 (3 n-1)/(n^2-1),Mod[n,2]==1}}],{n,20}]

FullSimplify[Piecewise[{{Missing["NotApplicable"],m==1&&n==1}},Min[(3 Min[m,n]-2)/(Min[m,n] Floor[Max[m,n]/2]),(3 Min[m,n]-1)/Floor[m n/2]]]/.m->n,n>0]

Table[({{\[Piecewise], ({{Missing["NotApplicable"], n==1}, {Min[((-2+3 n)/(n Floor[(n/2)])),((-1+3 n)/(Floor[((n^2)/2)]))], True}})}}),{n,20}]

Simplify[({{\[Piecewise], ({{Missing["NotApplicable"], n==1}, {Min[((-2+3 n)/(n Floor[(n/2)])),((-1+3 n)/(Floor[((n^2)/2)]))], True}})}}),n>1]

Factor@FullSimplify[Min[((-2+3 n)/(n Floor[(n/2)])),((-1+3 n)/(Floor[((n^2)/2)]))],Mod[n,2]==#]&/@{0,1}

King m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"King",{m,n}},"CheegerConstant"],
Piecewise[{{Missing["NotApplicable"],m==1&&n==1}},Min[(3 Min[m,n]-2)/(Min[m,n] Floor[Max[m,n]/2]),(3 Min[m,n]-1)/Floor[m n/2]]]
},{n,10},{m,n}],1],{_,x_,x_}]

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["CheegerConstant"]

seq=Table[GraphData[{"Knight",{n,n}},"CheegerConstant"],{n,20}]

Short answer: no — there is currently no known clean, general, rigorous formula for the Cheeger constant of the  n×n knight graph, and I cannot give a correct proof of one.

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["CheegerConstant"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"CheegerConstant"],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

DeleteCases[%,{_,_Missing,_}]

📌 Final honest conclusion
There is no known closed form for 
There is no simple geometric minimizer
The problem is nontrivial and open (in general form)

KP

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"KP",{m,n}},"CheegerConstant"],
Piecewise[{{Missing["NotApplicable"],m==1&&n==1},{Ceiling[m/2],n==1},{1/Floor[n/2],n>=2}}]
},{n,10},{m,10}],1],{_,x_,x_}]

Ladder

Entity["Graph",{"Ladder",n}]["CheegerConstant"]

Inferred for n > 8:

seq=Table[GraphData[{"Ladder",n},"CheegerConstant"],{n,20}]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

SeriesCoefficient[gf,{x,0,n}]

FullSimplify[%,n>=2]

FullSimplify[-((1+(((-1))^n)-2 n)/((-1+n) n)),Mod[n,2]==#]&/@{0,1}

Table[Piecewise[{{1,n==1},{(2/n),Mod[n,2]==0},{(2/(n-1)),Mod[n,2]==1}}],{n,20}]

LadderRung

seq=Table[GraphData[{"LadderRung",n},"CheegerConstant"],{n,20}]

LindgrenSousselier

seq=Table[GraphData[{"LindgrenSousselier",n},"CheegerConstant"],{n,11}]

LucasCube

seq=Table[GraphData[{"LucasCube",n},"CheegerConstant"],{n,15}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"CheegerConstant"],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["CheegerConstant"]

seq=Table[GraphData[{"MoebiusLadder",n},"CheegerConstant"],{n,3,25}]

Table[Piecewise[{{5/3,n==3}},2/Floor[n/2]],{n,3,25}]

Mycielski

Entity["Graph",{"Mycielski",n}]["CheegerConstant"]

seq=Table[GraphData[{"Mycielski",n},"CheegerConstant"],{n,11}]

Yes - that means my previous answer was wrong.

For `GraphData[{"Mycielski", n}]`, the indexing is the standard Mycielski sequence

* `n = 1`: `K1`
* `n = 2`: `K2`
* `n = 3`: `C5`
* `n = 4`: the Grötzsch graph

so your built-in values give

```wl
Piecewise[
    {
        {Missing["NotApplicable"], n == 1},
        {1, IntervalMemberQ[Interval[{2, 3}], n]},
        {8/5, n == 4}
    }
]
```

So it is definitely not a constant `1/2` or anything that simple.

Also, I checked the next one directly from the recursive Mycielski construction (by exact exhaustive search on the 23-vertex graph), and the next value is

```wl
27/11
```

so the beginning of the sequence is

```wl
{Missing["NotApplicable"], 1, 1, 8/5, 27/11}
```

Numerically:

```wl
{Missing["NotApplicable"], 1., 1., 1.6, 2.4545454545}
```

So the safest conclusion right now is:

* the exact known initial values are as above,
* there is no obvious simple closed form from the available data,
* and my earlier general formula was incorrect.

If you want, I can next derive the `8/5` for the Grötzsch graph explicitly, or give WL code that constructs `Mycielski[n]` recursively and computes the `n = 5` value exactly.

Necklace

seq=Table[GraphData[{"Necklace",n},"CheegerConstant"],{n,20}]

Table[Piecewise[{{2,n==1}},1/(2 Floor[n/2])],{n,20}]

Odd

Entity["Graph",{"Odd",n}]["CheegerConstant"]

seq=Table[GraphData[{"Odd",n},"CheegerConstant"],{n,7}]

OddCheegerKnown[n_Integer?Positive] := Piecewise[{
	{Missing["NotApplicable"], n == 1},
	{2, n == 2},
	{1, n == 3},
	{20/17, n == 4}
}]

and for general n >= 3,

1 <= GraphData[{"Odd", n}, "CheegerConstant"] <= n/(n - 1)

Paley

GraphData["Paley","CheegerConstant"]

Pan

Inferred for n > 16:

seq=Table[GraphData[{"Pan",n},"CheegerConstant"],{n,3,20}]

FullSimplify[FindSequenceFunction[DeleteMissing@seq,n-2],n>2]

Path

Entity["Graph",{"Path",n}]["CheegerConstant"]

seq=Table[GraphData[{"Path",n},"CheegerConstant"],{n,20}]

* Path P_n:
  h(P_n) = 1/floor(n/2),
  by taking an end segment of floor(n/2) vertices, which has exactly one boundary edge.

Table[Piecewise[{{Missing["NotApplicable"],n==1}},(1/(Floor[(n/2)]))],{n,20}]

PathComplement

seq=Table[GraphData[{"PathComplement",n},"CheegerConstant"],{n,20}]

Peisert

GraphData["Peisert","CheegerConstant"]

Pell

seq=Table[GraphData[{"Pell",n},"CheegerConstant"],{n,9}]

PlummerToft

seq=Table[GraphData[{"PlummerToft",n},"CheegerConstant"],{n,20}]

Prism

Entity["Graph",{"Prism",n}]["CheegerConstant"]

seq=Table[GraphData[{"Prism",n},"CheegerConstant"],{n,3,25}]

FindSequenceFunction[DeleteMissing@seq,n-2]//Head//Timing

Table[Piecewise[{{1,n==3||n==4||n==5}},2/Floor[n/2]],{n,3,25}]

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"CheegerConstant"],{n,20}]

Not yet, at least not with a lower-bound argument I would trust enough to call a proof.

For the n x n queen graph, two squares are adjacent exactly when they are in the same row, column, or diagonal. ([Wikipedia][1])

If S is any set of squares, with s = |S| <= n^2/2, and if

* r_i = |S intersect row i|,
* c_j = |S intersect column j|,
* d_k = |S intersect difference diagonal k|,
* e_l = |S intersect sum diagonal l|,

then the edge boundary is exactly

B(S) =
Sum_i r_i (n - r_i)

* Sum_j c_j (n - c_j)
* Sum_k d_k (L_k - d_k)
* Sum_l e_l (M_l - e_l),

where L_k and M_l are the corresponding diagonal lengths.

So the lower bound you want is precisely

B(S) >= n s

for every S with s <= n^2/2.

That is the right target, and the upper bound is easy from the two extremal constructions we already discussed. But I do not yet have the matching inequality.

The natural routes I tried all stall:

1. Split into rook part + bishop part.
   This explains the two equality patterns nicely:

* even n: half the rows,
* odd n: the smaller checkerboard color class.
  But I do not yet have a clean pair of complementary lower bounds that adds up to n s.

2. Spectral lower bound.
   The usual Cheeger-vs-lambda_2 route is too weak here; numerically the Laplacian gap is below 2n, so lambda_2/2 does not reach n.

3. Concentration on rows/columns vs diagonals.
   This feels most promising: one wants an "uncertainty principle" saying you cannot make all four line families simultaneously too concentrated. There is a related "Parallelogram Law" in the queen-graph literature, but I have not turned it into the inequality above. ([The Electronic Journal of Combinatorics][2])

So the honest status is:

* the formula h(Q_{n,n}) = n for n >= 2 still looks very plausible,
* the upper bound n is clean,
* the data n = 2, 3, 4 matches exactly,
* but I do not yet have a rigorous lower-bound proof.

A promising next attack would be a compression/majorization argument on the four line-count families.

[1]: https://en.wikipedia.org/wiki/Queen%27s_graph?utm_source=chatgpt.com "Queen's graph"
[2]: https://www.combinatorics.org/ojs/index.php/eljc/article/download/v8i1r29/pdf?utm_source=chatgpt.com "Values of Domination Numbers of the Queen's Graph"

Rook m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Rook",{m,n}},"CheegerConstant"],
Piecewise[{{Missing["NotApplicable"],m==1&&n==1},{Ceiling[n/2],m==1},{Ceiling[m/2],n==1}},Ceiling[Min[m,n]/2]]
},{n,20},{m,n}],1],{_,x_,x_}|{_,_GraphData,_}]//Quiet

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"CheegerConstant"],{n,20}]

FullSimplify[Piecewise[{{Missing["NotApplicable"],m==1&&n==1},{Ceiling[n/2],m==1},{Ceiling[m/2],n==1}},Ceiling[Min[m,n]/2]]/.m->n]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"CheegerConstant"],{n,20}]

FullSimplify[Piecewise[{{Missing["NotApplicable"],m==1&&n==1},{0,m==1||n==1},{(m n-m-n)/2,Mod[m,2]==0&&Mod[n,2]==0},{(m n-m-n)/2+1/(2 n),Mod[m,2]==0&&Mod[n,2]==1},{(m n-m-n)/2+1/(2 m),Mod[m,2]==1&&Mod[n,2]==0}},(m-1) (n-1)/2]/.m->n]

Table[Piecewise[{{Missing["NotApplicable"],n==1}},Floor[(n-1)^2/2]],{n,20}]

RookComplement m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"RookComplement",{m,n}},"CheegerConstant"],
Piecewise[{{Missing["NotApplicable"],m==1&&n==1},{0,m==1||n==1},{(m n-m-n)/2,Mod[m,2]==0&&Mod[n,2]==0},{(m n-m-n)/2+1/(2 n),Mod[m,2]==0&&Mod[n,2]==1},{(m n-m-n)/2+1/(2 m),Mod[m,2]==1&&Mod[n,2]==0}},(m-1) (n-1)/2]
},{n,20},{m,n}],1],{_,x_,x_}|{_,_GraphData,_}]//Quiet

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"CheegerConstant"],{n,4}]

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"CheegerConstant"],{n,7}]

Table[8/(3^(n-1)+3),{n,7}]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"CheegerConstant"],{n,6}]

Yes. And the answer is not 2.

I misidentified the graph before. If you write m = 2^(n - 1), the graph behind GraphData[{"SierpinskiTetrahedron", n}] has

|V| = 2 m^2 + 2,
|E| = 6 m^2,

exactly matching the MathWorld counts 2(4^(n - 1) + 1) and 6*4^(n - 1). That is the triangular surface mesh of a tetrahedron of side length m, not the "holey tetrix dual" I had in mind. ([MathWorld][1])

After rebuilding that graph model and solving the exact Cheeger problem by integer optimization for the first nontrivial cases, I get:

n = 1: 2
n = 2: 2
n = 3: 18/17
n = 4: 34/65

So the constant answer 2 is definitely wrong.

The values fit the formula

Piecewise[{{2, n == 1}, {(2^(n + 1) + 2)/(4^(n - 1) + 1), n >= 2}}]

equivalently, with m = 2^(n - 1),

h = (4 m + 2)/(m^2 + 1),    m >= 2.

That gives the sequence

{2, 2, 18/17, 34/65, 66/257, 130/1025, ...}.

What I can justify cleanly is the upper bound. For m >= 2 there is an "equatorial" balanced cut of the tetrahedral surface mesh with

|S| = m^2 + 1 = |V|/2
and
|\partial S| = 4 m + 2,

so

h <= (4 m + 2)/(m^2 + 1).    (my construction)

Then my exact MILP computations show equality for m = 2, 4, 8, i.e. n = 2, 3, 4.

So the most honest status is:

Conjectured exact formula:
Piecewise[{{2, n == 1}, {(2^(n + 1) + 2)/(4^(n - 1) + 1), n >= 2}}]

with exact verification now for n <= 4.

If you want the WL form only, use:

Piecewise[{{2, n == 1}, {(2^(n + 1) + 2)/(4^(n - 1) + 1), n >= 2}}]

The remaining missing piece is a general lower-bound proof that every S with |S| <= |V|/2 satisfies

|\partial S| >= ((4 m + 2)/(m^2 + 1)) |S|.

I do not have that proof yet, but this is much stronger than my earlier answer: the graph model is now correct, the old constant-2 claim is disproved, and the new formula is exact for the first four n.

[1]: https://mathworld.wolfram.com/SierpinskiTetrahedronGraph.html "https://mathworld.wolfram.com/SierpinskiTetrahedronGraph.html"

Spoke n×n

seq=Table[GraphData[{"Spoke",{n,n}},"CheegerConstant"],{n,5}]

StackedBook m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"StackedBook",{m,n}},"CheegerConstant"],
Piecewise[{{1,n==1||n==2||(n==3&&m<=2)},{(m+2)/(m+3),n==3&&m>=3}},1/Floor[n/2]]
},{n,10},{m,n}],1],{_,x_,x_}]

StackedBook n×n

seq=Table[GraphData[{"StackedBook",{n,n}},"CheegerConstant"],{n,10}]

StackedPrism m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"StackedPrism",{m,n}},"CheegerConstant"],
Piecewise[{{2/Floor[m/2],n==1}},Min[2/Floor[m/2],1/Floor[n/2]]]
},{m,3,8},{n,5}],1],{_,x_,x_}]

StackedPrism n×n

seq=Table[GraphData[{"StackedPrism",{n,n}},"CheegerConstant"],{n,3,5}]

Star

Entity["Graph",{"Star",n}]["CheegerConstant"]

seq=Table[GraphData[{"Star",n},"CheegerConstant"],{n,25}]

Sun

seq=Table[GraphData[{"Sun",n},"CheegerConstant"],{n,3,20}]

Table[Piecewise[{{(Floor[n^2/4]+2)/n,n<=7}},2],{n,3,20}]

Sunlet

seq=Table[GraphData[{"Sunlet",n},"CheegerConstant"],{n,3,20}]

FullSimplify[FindSequenceFunction[DeleteMissing@seq,n-2],n∈Integers]

Tetrahedral

seq=Table[GraphData[{"Tetrahedral",n},"CheegerConstant"],{n,6,10}]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"CheegerConstant"],{n,3,20}]

FullSimplify[2/Floor[Max[m,n]/2]/.m->n]

TorusGrid m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"TorusGrid",{m,n}},"CheegerConstant"],
2/Floor[Max[m,n]/2]
},{n,3,20},{m,n}],1],{_,x_,x_}|{_,_GraphData,_}]//Quiet

Transposition

Entity["Graph",{"Transposition",n}]["CheegerConstant"]

seq=Table[GraphData[{"Transposition",n},"CheegerConstant"],{n,6}]

So the honest status is:

TranspositionGraphCheegerConstant[n_] := Piecewise[
	{
		{Missing["NotApplicable"], n == 1},
		{n/2, Mod[n, 2] == 0}
	},
	Interval[{n/2, (n + 1)/2 - 1/n}]
]

and, separately, the natural conjectural exact formula would be

TranspositionGraphCheegerConstant[n_] := Piecewise[
	{
		{Missing["NotApplicable"], n == 1},
		{n/2, Mod[n, 2] == 0},
		{(n + 1)/2 - 1/n, Mod[n, 2] == 1}
	}
]

but I cannot currently promote that odd case from conjecture to theorem.

Yes. The even case is rigorous. The paper on the transposition network states that for even n, the bisection width is exactly n n! / 4. ([CSEE UMBC][1])

Since T_n has n! vertices, that exact bisection gives a set S with |S| = n!/2 and

|\partial S| / |S| = (n n! / 4) / (n! / 2) = n/2,

so h(T_n) <= n/2. ([CSEE UMBC][1])

On the other hand, T_n is d-regular with d = n(n - 1)/2, and its second adjacency eigenvalue is n(n - 3)/2, so d - lambda_2 = n. By the standard spectral Cheeger bound for regular graphs,

h(T_n) >= (d - lambda_2)/2 = n/2. ([arXiv][2])

Therefore, for even n,

h(T_n) = n/2. ([CSEE UMBC][1])

So the only unsettled part is the odd case.

[1]: https://www.csee.umbc.edu/~kalpakis/homepage/papers/nets-bisection.pdf?utm_source=chatgpt.com "On the Bisection idth of the Transposition"
[2]: https://arxiv.org/pdf/2204.03153?utm_source=chatgpt.com "Spectrum of the Transposition graph"

Trapezohedron

Entity["Graph",{"Trapezohedron",n}]["CheegerConstant"]

seq=Table[GraphData[{"Trapezohedron",n},"CheegerConstant"],{n,3,20}]

Table[Piecewise[{{1,Mod[n,2]==1}},(n+2)/(n+1)],{n,3,20}]

Triangular

seq=Table[GraphData[{"Triangular",n},"CheegerConstant"],{n,2,20}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"CheegerConstant"],{n,0,20}]

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"CheegerConstant"],{n,20}]

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"CheegerConstant"],{n,20}]

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"CheegerConstant"],{n,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"CheegerConstant"],{n,20}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"CheegerConstant"],{n,20}]

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"CheegerConstant"],{n,1,20,2}]

TruncatedSquareLattice n×n

seq=Table[GraphData[{"TruncatedSquareLattice",{n,n}},"CheegerConstant"],{n,10}]

seq=Table[Piecewise[{{2,n==1}},1/(2 Floor[n/2])],{n,20}]

FullSimplify[FindSequenceFunction[Rest@seq,n-1],n∈Integers]

TruncatedSquareLattice m×n

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"TruncatedSquareLattice",{m,n}},"CheegerConstant"],
Piecewise[{{2,m==n==1}},1/(2 Floor[Max[m,n]/2])]
},{n,20},{m,n}],1],{_,x_,x_}|{_,_GraphData,_}]//Quiet

Web

seq=Table[GraphData[{"Web",n},"CheegerConstant"],{n,3,20}]

Table[Piecewise[{{1,n==3}},4/(3 Floor[n/2])],{n,3,20}]

Wheel

Entity["Graph",{"Wheel",n}]["CheegerConstant"]

seq=Table[GraphData[{"Wheel",n},"CheegerConstant"],{n,4,20}]

FullSimplify[FindSequenceFunction[DeleteMissing@seq,n-3],n∈Integers]

FullSimplify[((-2 (1+(((-1))^n))+n (3+n))/((-1+n) n)),Mod[n,2]==#]&/@{0,1}

Table[Piecewise[{{((n+4)/n),Mod[n,2]==0},{((n+3)/(n-1)),Mod[n,2]==1}}],{n,4,20}]

WheelComplement

seq=Table[GraphData[{"WheelComplement",n},"CheegerConstant"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"CheegerConstant"],{n,2,20}]

WhiteCamel n×n

seq=Table[GraphData[{"Bishop",{n,n}},"CheegerConstant"],{n,{5}}]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"CheegerConstant"],{n,20}]