Graph Conductance

Author

Eric W. Weisstein
March 25, 2026

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

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

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

Sources

Wikipedia

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

Properties

0

A disconnected graph has conductance 0 iff some proper union of connected components has positive volume and its complement also has positive volume.

Regular

For any d-regular graph with degree d > 0, conductance = Cheeger constant/d

GraphDataCountTable

table=GraphDataCountTable["Conductance"]

DateString[]

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

Parametrized families

<<MathWorld`Graphs`

Alkane

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

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

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

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

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

AlternatingGroupGraph

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

Andrasfai

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

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

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

Antelope n×n

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

Antiprism

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

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

FindSequenceFunction[DeleteMissing@seq,n-2]

Apollonian

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

Barbell

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

FindSequenceFunction[DeleteMissing@seq,n-2]//Factor

Bishop n×n

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

BlackBishop n×n

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

Book

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

FindSequenceFunction[DeleteMissing@seq,n]//Factor

Bruhat

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

Camel n×n

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

Cameron

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

FindSequenceFunction[seq,n]

Centipede

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

FindSequenceFunction[seq,n]

CocktailParty

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

Complete

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

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

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

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

CompleteBipartite n×n

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

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

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

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

Table[((Ceiling[((n^2)/2)])/(n^2)),{n,20}]

CompleteBipartite m×n

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

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"Conductance"],
Piecewise[{{Max[m,n]/(Max[m,n]+2 Floor[Max[m,n]/2]),Mod[Min[m,n],2]==0},{Min[(Floor[Min[m,n]/2] Max[m,n]+Floor[Max[m,n] (Floor[Min[m,n]/2]+1)/Min[m,n]])/(Floor[Min[m,n]/2] Max[m,n]+Min[m,n] Floor[Max[m,n] (Floor[Min[m,n]/2]+1)/Min[m,n]]),((Floor[Min[m,n]/2]+1) Max[m,n]-Floor[Max[m,n] Floor[Min[m,n]/2]/Min[m,n]])/((Floor[Min[m,n]/2]+1) Max[m,n]+Min[m,n] Floor[Max[m,n] Floor[Min[m,n]/2]/Min[m,n]])],Mod[Min[m,n],2]==1}}]
},{n,20},{m,n}],1],{_,x_,x_}]

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"Conductance"],
Module[{r=Min[m,n],s=Max[m,n],p,b1,b2},If[Mod[r,2]==0,s/(s+2 Floor[s/2]),p=Floor[r/2];
b1=Floor[s (p+1)/r];
b2=Floor[s p/r];
Min[(p s+b1)/(p s+r b1),((p+1) s-b2)/((p+1) s+r b2)]]]
},{n,20},{m,n}],1],{_,x_,x_}]

Sort[DeleteCases[Flatten[Table[
{{m,n},
GraphData[{"CompleteBipartite",{m,n}},"Conductance"],
Min[((Floor[(1/2) Min[m,n]] Max[m,n]+Mod[Min[m,n],2] Floor[((Max[m,n] Ceiling[(1/2) Min[m,n]])/(Min[m,n]))])/(Floor[(1/2) Min[m,n]] Max[m,n]+Min[m,n] Floor[((Max[m,n] Ceiling[(1/2) Min[m,n]])/(Min[m,n]))])),((Ceiling[(1/2) Min[m,n]] Max[m,n]-Mod[Min[m,n],2] Floor[((Max[m,n] Floor[(1/2) Min[m,n]])/(Min[m,n]))])/(Ceiling[(1/2) Min[m,n]] Max[m,n]+Min[m,n] Floor[((Max[m,n] Floor[(1/2) Min[m,n]])/(Min[m,n]))]))]
},{n,20},{m,n}],1],{_,x_,x_}]]

Exactly. The surprise goes away once you look at the denominators.

For a set S in K_{m,n}, if S contains

* a vertices from the m-side, and
* b vertices from the n-side,

then the cut size is

|dS| = a n + b m - 2 a b.

So the numerator is already slightly two-variable, but still very tame.

The real difference is:

* Cheeger constant uses a denominator based on vertex count, essentially `|S| = a + b`.
* Conductance uses a denominator based on volume, namely

  vol(S) = a n + b m.

That is the whole story.

On a regular graph, `vol(S) = d |S|`, so conductance is just Cheeger constant divided by d. That is why on regular families the two invariants usually look equally simple.

But K_{m,n} is regular only when `m = n`. If `m != n`, the two sides have different degrees:

* vertices on one side have degree n,
* vertices on the other side have degree m.

So conductance does not just care how many vertices are in S. It cares which side they came from. Two subsets with the same size `a + b` can have different volumes `a n + b m`.

That forces the optimizer to solve a genuinely arithmetic balancing problem:

* maximize how many crossing edges are "saved" via the `2ab` term,
* while keeping the weighted size `a n + b m` near half the total volume.

Because of that weighted half-volume constraint, floors and remainders appear, and the winner can switch depending on `Max[m,n] mod Min[m,n]`. That is why the exact conductance formula has those annoying parity/remainder effects.

So:

* Cheeger constant is simpler because it is balancing plain cardinality.
* Conductance is more complicated because it is balancing weighted cardinality.
* The two coincide in complexity only in the regular case.

That is also why `K_{n,n}` suddenly becomes clean again: then both sides have the same degree n, so

vol(S) = n |S|,

and conductance collapses back to Cheeger constant divided by n.

If you want, I can write this as a compact proof sketch specialized to `K_{m,n}`.

CompleteTripartite n×n×n

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

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

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

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

CompleteTripartite k×m×n

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

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"Conductance"],
Min[Flatten[Table[If[0<x (m+n)+y (k+n)+z (k+m)≤k m+k n+m n,((x (m+n)+y (k+n)+z (k+m)-2 (x y+x z+y z))/(x (m+n)+y (k+n)+z (k+m))),∞],{x,0,k},{y,0,m},{z,0,n}],2]]
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

ChatGPT 5.4

Not in any really short way that I trust.

I checked small cases more carefully, and the exact minimizer type changes even within the same sorted parity class, so a compact parity-only `Piecewise[...]` is not enough.

For example, with `k <= m <= n` and parity pattern odd-even-even:

* `K_{1,2,4}` has

  ```wl
  4/7
  ```

  attained by `(x,y,z) = (0,1,3)`.

* `K_{3,4,6}` has

  ```wl
  7/13
  ```

  attained by `(x,y,z) = (2,2,2)`.

So even after sorting, the same parity class can produce different minimizer shapes. That is a good sign that there is no really clean small `Piecewise` formula in terms of just `Min`, `Max`, parity, and a few cases.

The clean exact form I would trust is still the finite minimization:

```wl
Min[
    Flatten[
        Table[
            If[
                0 < x (m + n) + y (k + n) + z (k + m) <= k m + k n + m n,
                (x (m + n) + y (k + n) + z (k + m) - 2 (x y + x z + y z))/(x (m + n) + y (k + n) + z (k + m)),
                Infinity
            ],
            {x, 0, k}, {y, 0, m}, {z, 0, n}
        ],
        2
    ]
]
```

If you want a somewhat cleaner exact version, I can next try to reduce it to a `Min[...]` over a much smaller set of candidate formulas, but I do not think it collapses to a short single `Piecewise[...]` analogous to the complete bipartite case.

CompleteTripartiteMinusPerfectMatching

seq=Table[GraphData[{"CompleteTripartiteMinusPerfectMatching",{2n,2n,2n}},"Conductance"],{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","Conductance"]

CrossedPrism

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

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

Crown

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

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

FindSequenceFunction[DeleteMissing@seq,n]//InputForm

Table[DifferenceRoot[Function[{\[FormalY],\[FormalN]},{1-\[FormalN]+(-1+\[FormalN])*\[FormalY][\[FormalN]]+(1+\[FormalN])*\[FormalY][1+\[FormalN]]==0,\[FormalY][1]==1}]][n],{n,10}]

bug(473018): FindGeneratingFunction[{1, 0, 1/3, 1/3, 2/5, 2/5, 3/7, 3/7, 4/9, 4/9}, x] gives incorrect result

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

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

Simplify[%,n>0]//InputForm

Table[DifferenceRoot[Function[{\[FormalY],\[FormalN]},{-2*(-1+\[FormalN])^2*\[FormalY][\[FormalN]]+(2+\[FormalN]-\[FormalN]^2)*\[FormalY][1+\[FormalN]]+(1+\[FormalN])*(2+\[FormalN])*\[FormalY][2+\[FormalN]]==0,\[FormalY][0]==2,\[FormalY][1]==1}]][n],{n,20}]

Series[gf,{x,0,10}]

CubeConnectedCycle

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

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

Cheeger constant is possibly 1/n, which would make conductance 1/(3 n)

ChatGPT 5.4 Heavy thinking 1

Here is the rigorous status I would use.

For `n >= 3`, `CCC_n = GraphData[{"CubeConnectedCycle", n}]` is a simple 3-regular graph on `n 2^n` vertices, with vertices `(x,y)` where `x` is an `n`-bit word and `y in {0,...,n-1}`; edges are the two cycle edges in the `y` coordinate and the cube edge `((x,y),(x xor 2^y,y))`. Wolfram’s official graph properties include `"CheegerConstant"` and `"Conductance"`, and for a regular graph conductance is the Cheeger constant divided by the common degree. ([Wolfram Documentation Center][1])

Let

```wl
S = { (x,y) : the first bit of x is 0 }.
```

Then `|S| = n 2^(n-1) = |V|/2`. The only edges leaving `S` are the cube edges in the layer corresponding to that fixed bit, so

```text
|∂S| = 2^(n-1).
```

Hence

```text
h(CCC_n) <= |∂S|/|S| = 1/n,
phi(CCC_n) <= |∂S|/(3 |S|) = 1/(3 n).
```

So `1/n` for the Cheeger constant and `1/(3 n)` for conductance are rigorous upper bounds. ([MathWorld][2])

There is also a rigorous exact bisection result: Bornstein et al. state that the minimum bisection width of the `(log n)`-dimensional cube-connected-cycles network is `n/2`; translating their notation to Wolfram’s `CCC_d` gives

```text
BW(CCC_d) = 2^(d-1).
```

So the cut above is an optimal bisection, and among bisections the ratio is exactly

```text
|∂S|/|S| = 1/d
```

and the corresponding conductance is exactly `1/(3 d)`. ([CMU School of Computer Science][3])

What I do **not** currently have is a rigorous proof or source that excludes a smaller non-bisection set with ratio `< 1/n`. So I would **not** record

```wl
GraphData[{"CubeConnectedCycle", n}, "CheegerConstant"] == 1/n
GraphData[{"CubeConnectedCycle", n}, "Conductance"] == 1/(3 n)
```

as fully verified for all `n >= 3` yet. What is verified is:

```wl
CubeConnectedCycleCheegerUpperBound[n_Integer?Positive] :=
  Piecewise[{{1/n, n >= 3}}, Missing["NotApplicable"]]

CubeConnectedCycleConductanceUpperBound[n_Integer?Positive] :=
  Piecewise[{{1/(3 n), n >= 3}}, Missing["NotApplicable"]]

CubeConnectedCycleBisectionWidth[n_Integer?Positive] :=
  Piecewise[{{2^(n - 1), n >= 3}}, Missing["NotApplicable"]]
```

So the honest rigorous summary is:

```wl
(* verified *)
h(CCC_n) <= 1/n
phi(CCC_n) <= 1/(3 n)
BW(CCC_n) = 2^(n - 1)   (* n >= 3 *)

(* plausible, matches n=3,4 built-ins, but not proved here *)
h(CCC_n) == 1/n
phi(CCC_n) == 1/(3 n)
```

If you want, I’ll try next to prove the missing lower bound `h(CCC_n) >= 1/n` directly, rather than only for bisections.

[1]: https://reference.wolfram.com/language/ref/GraphData.html "https://reference.wolfram.com/language/ref/GraphData.html"
[2]: https://mathworld.wolfram.com/Cube-ConnectedCycleGraph.html "https://mathworld.wolfram.com/Cube-ConnectedCycleGraph.html"
[3]: https://www.cs.cmu.edu/afs/cs.cmu.edu/project/phrensy/pub/papers/BornsteinLMSY97.pdf "https://www.cs.cmu.edu/afs/cs.cmu.edu/project/phrensy/pub/papers/BornsteinLMSY97.pdf"

ChatGPT 5.4 Heavy thinking 2

I tried to close the lower bound, but I do **not** currently have a rigorous proof or an accessible source showing that **every** set `S` in `CCC_n` satisfies `|∂S| >= |S|/n`. So I would **not** mark full `"CheegerConstant"` or `"Conductance"` as verified for all `n >= 3` yet. What I can justify rigorously is the exact **bisection** value, plus the corresponding global **upper bound**. ([Wolfram Documentation Center][1])

For `CCC_n`, MathWorld gives the standard model with vertex set
`{(x,y) : x in {0,1}^n, y in {0,...,n-1}}`,
`n 2^n` vertices total, and degree `3` for `n >= 3`. If you cut by one cube coordinate, e.g. take
`S = {(x,y) : x_1 = 0}`,
then `|S| = n 2^(n-1)` and the only crossing edges are the matching edges in that one coordinate, so `|∂S| = 2^(n-1)`. Therefore the vertex-count-normalized cut ratio is exactly `1/n`; with the usual volume normalization on this 3-regular graph, the same cut has value `1/(3 n)`. This matches your `1/9, 1/12` data at `n = 3, 4`. ([MathWorld][2])

What is fully rigorous on the lower-bound side is the **bisection width**. Bornstein et al. prove that the bisection width of the `(log n)`-dimensional cube-connected-cycles network is `n/2`. Translating their parameter to Wolfram/MathWorld notation (`n = 2^d`) gives
`BW(CCC_d) = 2^(d-1)`.
So among **bisections**, the exact vertex-normalized ratio is
`2^(d-1)/(d 2^(d-1)) = 1/d`,
and the corresponding 3-regular volume-normalized ratio is `1/(3 d)`. ([CMU School of Computer Science][3])

So the clean rigorous status is:

* **Verified:** exact bisection width `2^(n - 1)` for `n >= 3`
* **Verified:** global upper bound `<= 1/n` for the vertex-normalized cut ratio
* **Verified:** global upper bound `<= 1/(3 n)` for the corresponding volume-normalized cut ratio
* **Not yet verified by me:** that these upper bounds are the actual global minima over **all** subsets, not just bisections. ([CMU School of Computer Science][3])

WL forms I would use are:

```wl
CubeConnectedCycleBisectionWidth[n_Integer?Positive] :=
  Piecewise[{{2^(n - 1), n >= 3}}, Missing["NotApplicable"]]

CubeConnectedCycleCheegerUpperBound[n_Integer?Positive] :=
  Piecewise[{{1/n, n >= 3}}, Missing["NotApplicable"]]

CubeConnectedCycleConductanceUpperBound[n_Integer?Positive] :=
  Piecewise[{{1/(3 n), n >= 3}}, Missing["NotApplicable"]]

CubeConnectedCycleCheegerAppearsToBe[n_Integer?Positive] :=
  Piecewise[{{1/n, n >= 3}}, Missing["NotApplicable"]]

CubeConnectedCycleConductanceAppearsToBe[n_Integer?Positive] :=
  Piecewise[{{1/(3 n), n >= 3}}, Missing["NotApplicable"]]
```

And, for provenance, Wolfram’s GraphData source-information page says most GraphData properties are computed in the Wolfram Language, with some taken from the literature and cross-checked against known relations. ([Wolfram Documentation Center][1])

The next sensible move is to treat the exact full conductance formula as **plausible but not yet rigorous**, unless you want me to keep pushing specifically on the missing lower bound `|∂S| >= |S|/n`.

[1]: https://reference.wolfram.com/language/note/GraphDataSourceInformation.html "https://reference.wolfram.com/language/note/GraphDataSourceInformation.html"
[2]: https://mathworld.wolfram.com/Cube-ConnectedCycleGraph.html "https://mathworld.wolfram.com/Cube-ConnectedCycleGraph.html"
[3]: https://www.cs.cmu.edu/afs/cs.cmu.edu/project/phrensy/pub/papers/BornsteinLMSY97.pdf "https://www.cs.cmu.edu/afs/cs.cmu.edu/project/phrensy/pub/papers/BornsteinLMSY97.pdf"

Cycle

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

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

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

CycleComplement

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

bug(473019):  FindGeneratingFunction[{1, 0, 1/2, 1/3, 1/2, 2/5, 1/2, 3/7, 1/2, 4/9, 1/2, 5/11, 1/2, 6/13, 1/2, 7/15, 1/2, 8/17}, x] returns result in unusable DifferentialRoot form

gf=(x^3)FindGeneratingFunction[seq,x]

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

Series[gf,{x,0,2}]//Timing

DiagonalIntersection

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

Dipyramid

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

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

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

DorogovtsevGoltsevMendes

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

DoubleCone

Inferred for n > 10:

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

Empty

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

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

ChatGPT 5.4 Heavy thinking

Yes, I would use `0` there too, but as a **convention**, not as a direct consequence of the standard formula.

The usual conductance definition is
[
\phi(G)=\min_{\emptyset \neq S \subset V}\frac{|E(S,V\setminus S)|}{\min{\mathrm{vol}(S),\mathrm{vol}(V\setminus S)}},
]
with `vol(S)` the sum of degrees in `S`. That is the standard volume-normalized cut definition, and MathWorld describes conductance as the normalized variant of the Cheeger constant obtained by replacing set size with volume. ([Yale Computer Science][1])

For `K_1`, there is **no** nonempty proper subset `S`, so the minimization domain is empty. More generally, for any edgeless graph, all volumes are `0`, so the denominator degenerates as well. Thus the raw mathematical definition does not assign a value here. ([Yale Computer Science][1])

So I would separate it this way:

* **mathematical standard definition:** degenerate / undefined on `K_1`
* **recommended GraphData convention:** `0`
* **reason for the convention:** it makes the empty-graph family uniform and matches the intuition of “no boundary edges, hence no expansion” better than `Missing["NotApplicable"]` ([Wolfram Documentation Center][2])

So, for your test/design question: **yes, I would set graph conductance of `K_1` to `0` as well.**

If useful, I can also suggest a matching test for `"Conductance"` over `GraphData["Empty"]`.

[1]: https://www.cs.yale.edu/homes/vishnoi/Lxb-Web.pdf "Lx = b Laplacian Solvers and Their Algorithmic Applications"
[2]: https://reference.wolfram.com/language/ref/GraphData.html?utm_source=chatgpt.com "GraphData - Wolfram Language Documentation"

FibonacciCube

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

Fiveleaper n×n

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

Flower

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

FoldedCube

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

FindSequenceFunction[seq,n-1]

Gear

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

seq=Table[(Floor[(3 n-2)/5]+2)/(5 Floor[(3 n-2)/5]+2),{n,3,20}]

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

Giraffe n×n

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

Goldberg

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

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

Grid n×n

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

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

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

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

Grid m×n

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

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"Conductance"],
Piecewise[{{Missing["NotApplicable"],m==n==1},{Max[m,n]/((4 Max[m,n]-2) Floor[Min[m,n]/2]-Max[m,n]),Mod[Min[m,n],2]==0&&Max[m,n]==Min[m,n]+1},{1/3,m==3&&n==3}},Min[m,n]/((4 Min[m,n]-2) Floor[Max[m,n]/2]-Min[m,n])]
},{n,20},{m,n}],1],{_,x_,x_}|{_,_GraphData,_}]//Quiet

Grid n×n×n

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

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

Conjecture:

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

with the caveat that I currently regard only the even branch as fully rigorous from the argument above.

Table[Piecewise[{
{Missing["NotApplicable"],n==1},
{1/(3 n-3),n>=2&&Mod[n,2]==0},
{Min[(n^2+n+1)/(3 (n^3-n^2-1)),2 n/(3 n^2-1)],n>=3&&Mod[n,2]==1}
}],{n,10}]

"proved exact for even n, proved upper bound for odd n."

Grid k×m×n

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

Sort@DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"Conductance"],
XXX
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

HalvedCube

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

FindSequenceFunction[Rest@seq,n-1]

Hanoi

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

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

Helm

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

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

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

Hypercube

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

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

KC

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"KC",{m,n}},"Conductance"],
Piecewise[{{1/Floor[n/2],m==1},{Ceiling[Min[m,3]/2]/(m+1),n==3}},2/((m+1) Floor[n/2])]
},{n,3,10},{m,10}],1],{_,x_,x_}]

Keller

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

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

Table[Piecewise[{{1,n==1}},2 (4^(n-1)-3^(n-1))/(4^n-3^n-n)],{n,5}]

King n×n

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

Conjecture:

Piecewise[{{2/3,n==2},{9/19,n==3},{(3 n-2)/(2 (n-1) (2 n-1)),Mod[n,2]==0},{(3 n-1)/(4 n^2-6 n-2),Mod[n,2]==1}}]

One important correction to my earlier claim: I have now checked this corrected formula against exact optimization for small n, and it matches there, but I have not yet given a full all-n lower-bound proof that no other shape does better. So this is now the corrected exact small-n behavior and the corrected general formula, but I should label the general all-n statement as verified/conjectural until that lower bound is written out.

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

Yes, but I need to be careful about what is fully proved.

I can give a rigorous sharp lower bound **once the set has been compressed to a top-left Ferrers shape** (equivalently, columns are contiguous from the top and their heights are nonincreasing from left to right). Within that class, the lower bound is exact and gives the same formulas as the upper-bound constructions.

The step I do **not** yet have fully written out is the global compression lemma saying that every minimizing set in the king graph can be replaced by such a Ferrers set without increasing conductance. That is the only missing global step.

Here is the rigorous part.

---

## 1. Ferrers-shape reduction

Write the (n \times n) king graph as (K_n = P_n \boxtimes P_n).

Consider a set (S) of the form

[
S = {(i,j) : 1 \le i \le k,\ 1 \le j \le a_i},
\qquad
n \ge a_1 \ge a_2 \ge \cdots \ge a_k \ge 1.
]

So the column heights are (a_1,\dots,a_k), top-justified and nonincreasing.

---

## 2. Boundary formulas for a Ferrers set

Let (\partial S) denote the edge boundary.

There are two kinds of boundary edges:

* vertical edges inside a column, at the bottom of a partial column;
* edges between adjacent columns.

### Vertical contribution

A column of height (a_i) contributes one vertical boundary edge iff (a_i < n). So

[
B_{\mathrm{vert}} = #{i : a_i < n}.
]

### Contribution between adjacent columns

For adjacent columns of heights (a \ge b), the number of crossing edges between those two columns is

[
B(a,b)=
\begin{cases}
0, & a=b=n,[4pt]
2, & a=b<n,[4pt]
3(a-b), & n>a>b>0,[4pt]
3(a-b)-1, & a=n>b>0,[4pt]
3a-1, & n>a>b=0,[4pt]
3n-2, & a=n,\ b=0.
\end{cases}
]

This is a direct count of horizontal plus diagonal edges across the interface.

So if we set (a_{k+1}=0), then

[
|\partial S|
============

#{i : a_i < n}
+
\sum_{i=1}^{k} B(a_i,a_{i+1}).
]

That formula is exact.

---

## 3. Volume formulas

Let (\operatorname{vol}(S)) be the sum of degrees of the vertices of (S).

For a full leftmost column, the degree sum is

[
5n-4.
]

For a full interior column, it is

[
8n-6.
]

For a partial interior column of height (p), it is

[
8p-3.
]

For a partial leftmost column of height (p), it is

[
5p-2.
]

These are exact.

---

## 4. Why the extremal Ferrers shape has at most one partial column

Now suppose (S) is a Ferrers set with at least two partial columns. Then one can move a cell from a later partial column to an earlier partial column. This:

* does **not increase** the boundary,
* and does **not decrease** the volume.

So repeated balancing pushes all partial mass leftward, and the optimal Ferrers set has the form:

* some number (t) of full columns,
* followed by at most one partial column of height (p),
* followed by zero columns.

So the only Ferrers candidates that matter are

[
(a_1,\dots,a_k) = (\underbrace{n,\dots,n}_{t\text{ times}}, p),
\qquad 0 \le p < n.
]

---

## 5. Exact formulas for these extremal Ferrers shapes

Now everything becomes explicit.

### Case A: full strip only

If (p=0), so (S) is exactly (t) full columns, then

[
|\partial S| = 3n-2,
]

and

[
\operatorname{vol}(S) = (5n-4) + (t-1)(8n-6).
]

Hence

[
\phi(S)=\frac{3n-2}{(5n-4)+(t-1)(8n-6)}.
]

This decreases with (t), so under the half-volume constraint the best such set is the largest allowable strip.

For even (n), that is (t=n/2), giving

[
\phi(S) = \frac{3n-2}{2(n-1)(2n-1)}.
]

### Case B: (t) full columns plus one partial column of height (p)

If (1 \le p < n), then a direct substitution into the boundary formula gives

[
|\partial S| = 3n-1,
]

independent of (t) and (p).

The volume is

[
\operatorname{vol}(S)
=====================

(5n-4) + (t-1)(8n-6) + (8p-3).
]

So

[
\phi(S)
=======

\frac{3n-1}{(5n-4) + (t-1)(8n-6) + (8p-3)}.
]

Again this decreases as (t) and (p) increase, so under the half-volume constraint the best one is the largest allowable choice.

For odd (n=2m+1), the half-volume constraint is met exactly by

[
t=m,\qquad p=m,
]

which gives

[
\operatorname{vol}(S)=4n^2-6n-2
]

and therefore

[
\phi(S)=\frac{3n-1}{4n^2-6n-2}.
]

That is the odd formula I gave before.

---

## 6. What this proves

So, **rigorously within the Ferrers class**, the minimum conductance is:

[
\Phi_{\mathrm{Ferrers}}(King_{n,n})=
\begin{cases}
\dfrac{3n-2}{2(n-1)(2n-1)}, & n \text{ even},[8pt]
\dfrac{3n-1}{4n^2-6n-2}, & n \text{ odd and } n \ge 5,
\end{cases}
]

with (n=3) exceptional, giving (9/19).

---

## 7. What remains for the full graph

To conclude this for **all** subsets (S), one still needs:

> A compression lemma showing that repeated upward and leftward compressions do not increase edge boundary and do not decrease volume, so a conductance minimizer may be taken to be Ferrers.

That is standard in flavor for edge-isoperimetric problems on products, but I do not want to pretend I have fully written that part down yet.

So the honest status is:

* **proved exactly for compressed Ferrers sets**;
* **full lower bound for arbitrary sets** is reduced to that compression lemma;
* I do not yet have the full polished proof of that lemma.

If you want, I can next write out the exchange argument in full detail for the Ferrers case, so that part is completely airtight.

King m×n

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

Knight n×n

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

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

Not yet, not honestly.

I can prove the upper bound, but I do not currently have a complete lower-bound proof showing that no other cut beats it for all even n.

So the rigorous status is:

[
\phi(K_n)=
\begin{cases}
\mathrm{Missing}["NotApplicable"], & n=1,[4pt]
1, & n=2,[4pt]
\frac14, & n=3,[4pt]
\frac16, & n=4,[4pt]
\mathrm{Missing}["NotAvailable"], & n \ge 5
\end{cases}
]

and the proved upper bound is

[
\phi(K_n)\le
\begin{cases}
\frac{n-2}{4(n-1)}, & n \ge 4,\ \operatorname{Mod}(n,2)=0,[8pt]
\frac14, & n \ge 5,\ \operatorname{Mod}(n,4)=1.
\end{cases}
]

So the exact "proved-only" WL function should be

```wl
KnightGraphConductance[n_] := Piecewise[
    {
        {Missing["NotApplicable"], n == 1},
        {1, n == 2},
        {1/4, n == 3},
        {1/6, n == 4},
        {Missing["NotAvailable"], n >= 5}
    }
]
```

and the separate rigorous upper bound is

```wl
KnightGraphConductanceUpperBound[n_] := Piecewise[
    {
        {Missing["NotApplicable"], n == 1},
        {1, n == 2},
        {1/4, n == 3},
        {(n - 2)/(4 (n - 1)), n >= 4 && Mod[n, 2] == 0},
        {1/4, n >= 5 && Mod[n, 4] == 1},
        {Missing["NotAvailable"], n >= 5 && Mod[n, 4] == 3}
    }
]
```

The conjectured exact formula is still

[
\phi(K_n)=
\begin{cases}
\frac{n-2}{4(n-1)}, & \operatorname{Mod}(n,2)=0,[8pt]
\frac14, & \operatorname{Mod}(n,2)=1,\ n \ge 3,
\end{cases}
]

but I do not have a rigorous proof of the lower bound for the even branch.

The specific reason I am stopping there is that the natural 2 x 2 block reduction is not enough: partial fillings of a block can interact with diagonal block-neighbors in a way that defeats the naive blockwise lower-bound argument. So I would be overstating things if I wrote the even branch as proved.

If you want, I can keep trying, but at the moment the honest rigorous answer is "not yet."

Conjecture:

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

Knight m×n

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

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

KP

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"KP",{m,n}},"Conductance"],
Piecewise[{{Missing["NotApplicable"],m==n==1},{Ceiling[m/2]/(m-1),n==1},{3/7,m==2&&n==3}},1/(Floor[n/2] (m+1)-1)]
},{n,10},{m,10}],1],{_,x_,x_}]

Ladder

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

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

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

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

LadderRung

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

LindgrenSousselier

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

Table[Piecewise[{{(5 n+18)/(45 n+18),Mod[n,9]==0},{(2 n+7)/(18 n+9),Mod[n,9]==1}},(n+4)/(9 n+6)],{n,11}]

LucasCube

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

Yes, you are right. I was wrong about the n = 5 value.

Using your GraphData output, the values currently available are

Table[GraphData[{"LucasCube", n}, "Conductance"], {n, 6}]

=
{Missing["NotApplicable"], 1, 1, 1/3, 1/4, 1/5}

so the corrected formula that matches all available Wolfram values is

Piecewise[{{1, n <= 3}}, 1/(n - 1)]

for the valid n in this family. The standard Lucas-cube definition is the usual one: vertices are length-n binary strings with no consecutive 1s cyclically, and the classical decomposition is
Lambda_n = Gamma_(n - 1) union Gamma_(n - 3), with exactly one bridging edge from each Gamma_(n - 3) vertex into the Gamma_(n - 1) part. ([MathWorld][1])

So the corrected conjectural conductance formula is

Piecewise[{{1, n <= 3}}, 1/(n - 1)]

not my earlier 1/(2 Floor[n/2] - 1).

At this point, I do not have a rigorous proof of that conductance formula. What I can say honestly is:

* it matches the available GraphData values exactly for n = 2, 3, 4, 5, 6;
* my earlier pattern was incorrect;
* the standard recursive structure of Lucas cubes is consistent with trying to prove such a formula inductively, but I have not completed that proof. ([fq.math.ca][2])

In your preferred WL form, the current best expression is:

```wl
Piecewise[{{1, n <= 3}}, 1/(n - 1)]
```

If you want, I can now try to prove the upper and lower bounds separately for this formula.

[1]: https://mathworld.wolfram.com/LucasCubeGraph.html?utm_source=chatgpt.com "Lucas Cube Graph -- from Wolfram MathWorld"
[2]: https://www.fq.math.ca/Scanned/39-1/munarini.pdf "fq2001.pdf"

MengerSponge

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

MoebiusLadder

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

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

Table[Piecewise[{{2/3,n==2},{5/9,n==3},{2/(3 Floor[n/2]),n>=4}}],{n,3,25}]

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

ChatGPT 5.4 Heavy thinking

Yes. Using the standard graph-theoretic Cheeger constant
[
h(G)=\min_{0<|S|\le |V(G)|/2}\frac{|\partial S|}{|S|},
]
and the canonical Möbius ladder model (M_n\cong \mathrm{Ci}*{2n}(1,n)), the exact value for `{"MoebiusLadder", n}` is as follows. The Wolfram docs describe `{"MoebiusLadder", n}` as an n-sided prism graph with a half-twist, and MathWorld identifies it with the circulant graph (\mathrm{Ci}*{2n}(1,n)). ([Wolfram Documentation][1])

[
h(M_n)=
\begin{cases}
2, & n=2,[4pt]
5/3, & n=3,[4pt]
4/n, & n\ge 4 \text{ even},[4pt]
4/(n-1), & n\ge 5 \text{ odd}.
\end{cases}
]

Equivalently, for (n\ge 4),
[
h(M_n)=\frac{2}{\lfloor n/2\rfloor}.
]

Wolfram Language form:

```wl
MoebiusLadderCheegerConstant[n_Integer?Positive] :=
  Piecewise[
    {
      {2, n == 2},
      {5/3, n == 3},
      {4/n, EvenQ[n] && n >= 4},
      {4/(n - 1), OddQ[n] && n >= 5}
    },
    Missing["NotApplicable"]
  ]
```

Proof. Let the (n) rungs be (P_0,\dots,P_{n-1}), each with 2 vertices. For (S \subseteq V(M_n)), define
[
x_i := |S \cap P_i| \in {0,1,2},
\qquad
s:=|S|=\sum_i x_i.
]
Each rung contributes 1 boundary edge exactly when (x_i=1). Also, between consecutive rungs (P_i) and (P_{i+1}), the two connecting edges form a perfect matching, so at least (|x_i-x_{i+1}|) of those two edges lie in the boundary. Therefore
[
|\partial S|
\ge
\sum_i \mathbf{1}*{x_i=1} + \sum_i |x_i-x*{i+1}|.
\tag{1}
]

Now assume (2 \le s \le n).

If some (x_i=2), then since the average occupancy is at most 1, some (x_j=0). On the cyclic sequence ((x_i)), going from 0 to 2 and back forces
[
\sum_i |x_i-x_{i+1}| \ge 4,
]
hence (|\partial S| \ge 4).

If all (x_i \le 1), then either all (x_i=1), which can happen only when (s=n), and then (|\partial S|=n\ge 4); or else the 0-1 cyclic sequence has at least two transitions, so
[
\sum_i |x_i-x_{i+1}| \ge 2.
]
Since (s=\sum_i \mathbf{1}_{x_i=1}\ge 2), (1) again gives (|\partial S|\ge 4).

So every (S) with (2\le |S|\le n) satisfies
[
|\partial S|\ge 4.
\tag{2}
]

Also, (M_n) is cubic, so
[
3|S| = 2|E(S)| + |\partial S|.
]
Reducing mod 2 gives
[
|\partial S| \equiv |S| \pmod 2.
\tag{3}
]
Hence if (|S|) is odd and at least 3, then by (2) and (3),
[
|\partial S|\ge 5.
\tag{4}
]

For the upper bound, let (k=\lfloor n/2\rfloor), and take (A) to be (k) consecutive rungs. Then (|A|=2k\le n), and exactly four edges leave (A), so
[
h(M_n)\le \frac{4}{2k}=\frac{2}{k}.
\tag{5}
]

For the lower bound:

* if (|S|) is even, then by (2),
  [
  \frac{|\partial S|}{|S|}\ge \frac{4}{|S|}\ge \frac{4}{2k}=\frac{2}{k};
  ]

* if (|S|) is odd, then by (4),
  [
  \frac{|\partial S|}{|S|}\ge \frac{5}{|S|}.
  ]

If (n=2k) is even, then (|S|\le 2k-1) for odd (|S|), so
[
\frac{5}{|S|}\ge \frac{5}{2k-1} > \frac{2}{k}.
]
If (n=2k+1) is odd and at least 5, then
[
\frac{5}{|S|}\ge \frac{5}{2k+1}\ge \frac{2}{k},
]
with equality only at (n=5).

Therefore for all (n\ge 4),
[
h(M_n)=\frac{2}{\lfloor n/2\rfloor},
]
which is exactly the even/odd piecewise form above. The remaining small cases are direct:
(h(M_2)=2) and (h(M_3)=5/3).

Computed in this session: exhaustive search for (n=2,\dots,12) matches the formula exactly.

As a corollary, since conductance is Cheeger constant divided by the common degree for regular graphs, the conductance of `{"MoebiusLadder", n}` is (h(M_n)/3). ([MathWorld][2])

[1]: https://reference.wolfram.com/language/ref/GraphData.html "https://reference.wolfram.com/language/ref/GraphData.html"
[2]: https://mathworld.wolfram.com/CheegerConstant.html "https://mathworld.wolfram.com/CheegerConstant.html"

Mycielski

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

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

Necklace

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

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

Odd

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

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

I would not write a general exact formula from those data alone.

For the odd graph O_n = K(2 n - 1, n - 1), the graph is n-regular, so

`Conductance[O_n] = CheegerConstant[O_n]/n`

for the usual definitions of conductance and edge-isoperimetric number on a regular graph. ([uvm.edu][1])

So the values you have are consistent with

* `n == 2`: `1`
* `n == 3`: `1/3`

since `O_2 = K_3` and `O_3` is the Petersen graph. ([Wikipedia][2])

What I could verify is this:

* The odd graph `O_n` is the Kneser graph `K(2 n - 1, n - 1)`, and its adjacency eigenvalues are `(-1)^j (n - j)`, so the second-largest adjacency eigenvalue is `n - 2`. Hence the smallest positive Laplacian eigenvalue is `n - (n - 2) = 2`. ([Wikipedia][2])
* Therefore the standard spectral lower bound gives
  `CheegerConstant[O_n] >= 1`,
  hence
  `Conductance[O_n] >= 1/n`. ([Wikipedia][3])
* A 2020 paper on Cheeger constants for distance-regular graphs treats odd graphs and proves only the upper bound `CheegerConstant[O_n] <= 2`, which translates to
  `Conductance[O_n] <= 2/n`. It does this by exhibiting a large induced subgraph isomorphic to the doubled odd graph `dO_(n-2)`. 

So the rigorously supported general statement I can give is

```wl
1/n <= GraphData[{"Odd", n}, "Conductance"] <= 2/n
```

and at present I would only record the exact small cases as

```wl
Piecewise[{
    {1, n == 2},
    {1/3, n == 3}
}]
```

unless you want me to try to derive the `n == 4` case explicitly from scratch and see whether it is indeed `5/17`.

[1]: https://www.uvm.edu/~mrombach/395_week9.pdf?utm_source=chatgpt.com "Cheeger constant and conductance"
[2]: https://en.wikipedia.org/wiki/Kneser_graph?utm_source=chatgpt.com "Kneser graph"
[3]: https://en.wikipedia.org/wiki/Cheeger_constant_%28graph_theory%29?utm_source=chatgpt.com "Cheeger constant (graph theory)"

Paley

GraphData["Paley","Conductance"]

Pan

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

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers]//Factor

Path

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

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

FullSimplify[FindSequenceFunction[Drop[seq,2],n-2],n∈Integers]//Factor

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

PathComplement

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

FullSimplify[FindSequenceFunction[Drop[seq,2],n-2],n∈Integers]

Peisert

GraphData["Peisert","Conductance"]

Pell

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

PlummerToft

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

Prism

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

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

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

bug(473024):  Overly complicated result the second time FindGeneratingFunction[Table[Piecewise[{{1/3, n == 3}}, 2/(3 Floor[n/2])], {n, 3, 25}], x] is evaluated

gf=(x^3)FindGeneratingFunction[seq,x]

FullSimplify[gf]

Series[gf,{x,0,10}]

bug(473025): Overly complicated Piecewise from FindSequenceFunction[Table[Piecewise[{{1/3, n == 3}}, 2/(3 Floor[n/2])], {n, 3, 25}], n - 2]

FindSequenceFunction[DeleteMissing@seq,n-2]

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

Queen n×n

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

Rook n×n

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

FullSimplify[FindSequenceFunction[Drop[seq,1],n-1],n∈Integers]//Factor

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

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

Factor[FullSimplify[Piecewise[{{Missing["NotApplicable"],m==n==1},{((Ceiling[(1/2) Max[m,n]])/(m+n-2)),Min[m,n]==1}},((Ceiling[(1/2) Min[m,n]])/(m+n-2))]/. m->n]]

Rook m×n

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Rook",{m,n}},"Conductance"],
Piecewise[{{Missing["NotApplicable"],m==n==1},{Ceiling[Max[m,n]/2]/(m+n-2),Min[m,n]==1}},Ceiling[Min[m,n]/2]/(m+n-2)]
},{n,20},{m,n}],1],{_,x_,x_}|{_,_GraphData,_}]//Quiet

RookComplement n×n

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

RookComplement m×n

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

SierpinskiCarpet

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

SierpinskiGasket

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

SierpinskiTetrahedron

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

Spoke n×n

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

StackedBook m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"StackedBook",{m,n}},"Conductance"],
Piecewise[{{1,n==1},{(m+1)/(3 m+1),n==2},{3/7,n==3&&m==1},{(m+Floor[(2 m+1)/5]+1)/(3 m+5 Floor[(2 m+1)/5]+1),n==3&&m>=2}},(m+1)/((4 m+2) Floor[n/2]-m-1)]
},{n,10},{m,n}],1],{_,x_,x_}]

StackedBook n×n

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

StackedPrism m×n

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

StackedPrism n×n

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

Star

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

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

Sun

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

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

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

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

Sunlet

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

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

Tetrahedral

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

TorusGrid n×n

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

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

TorusGrid m×n

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

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"TorusGrid",{m,n}},"Conductance"],
Piecewise[{{1/Max[m,n],Mod[Max[m,n],2]==0},{1/(Max[m,n]-1),Mod[Max[m,n],2]==1}}]
},{n,3,20},{m,3,n}],1],{_,x_,x_}|{_,_GraphData,_}]//Quiet

Transposition

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

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

Yes. Translating the earlier Cheeger-status statement to conductance gives this.

The transposition graph `T_n` is `Binomial[n, 2]`-regular, and for a `d`-regular graph one has `Conductance = CheegerConstant/d`. Also, Kalpakis-Yesha state that the bisection width of `T_n` is exactly `n n!/4` for even `n`, while for odd `n` it is `(1 + o(1)) n n!/4`, and the transposition-graph spectrum gives second adjacency eigenvalue `n (n - 3)/2`. Combining these with the standard spectral lower bound gives the exact even branch and the same odd-case status you quoted earlier. 

So the direct WL translation is

```wl
Piecewise[
    {
        {1, n == 2},
        {1/(n - 1), Mod[n, 2] == 0},
        {Interval[{1/(n - 1), (n + 2)/n^2}], Mod[n, 2] == 1}
    }
]
```

Here the odd interval comes from dividing your earlier odd Cheeger interval
`Interval[{n/2, (n + 1)/2 - 1/n}]`
by `Binomial[n, 2]`, so
`(n/2)/Binomial[n, 2] = 1/(n - 1)` and
`((n + 1)/2 - 1/n)/Binomial[n, 2] = (n + 2)/n^2`. 

Separately, the corresponding natural conjectural exact formula is

```wl
Piecewise[
    {
        {1, n == 2},
        {1/(n - 1), Mod[n, 2] == 0},
        {(n + 2)/n^2, Mod[n, 2] == 1}
    }
]
```

This gives `5/9` at `n == 3`, matching your `GraphData` value. The even branch is rigorous; the odd exact branch is still conjectural. ([UMBC CSEE][1])

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

Trapezohedron

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

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

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

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

Triangular

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

TriangularGrid

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

Not in a form I would trust enough to state as a closed formula yet.

For the triangular grid graph
[
T_n=\operatorname{GraphData}[{"TriangularGrid",n}],
]
the standard model is the equilateral triangle with (n+1) vertices on each side; it has
[
|V(T_n)|=\frac{(n+1)(n+2)}{2},\qquad |E(T_n)|=\frac{3n(n+1)}{2}.
]
So the total volume is
[
\operatorname{vol}(T_n)=2|E(T_n)|=3n(n+1).
]
That part is standard. ([MathWorld][1])

The difficulty is that conductance is
[
\Phi(T_n)=\min_{\emptyset\neq S\subsetneq V(T_n)}
\frac{|\partial_E S|}{\min(\operatorname{vol}(S),\operatorname{vol}(V\setminus S))},
]
and (T_n) is not regular: boundary vertices have degree (2) or (4), while interior vertices have degree (6). So, unlike the Cheeger constant (h(T_n)), this is not a fixed multiple of the edge-expansion by cardinality. The minimizing sets for conductance are not obviously the same corner triangles that minimize the unweighted ratio.

What I am confident about is this exact initial segment:
[
\Phi(T_1)=1,\quad
\Phi(T_2)=\frac12,\quad
\Phi(T_3)=\frac38,\quad
\Phi(T_4)=\frac14,\quad
\Phi(T_5)=\frac{2}{11}.
]

Past that, I do not yet have a proved closed form. The staircase packings I checked strongly suggest
[
\Phi(T_6)=\frac{5}{31},\quad
\Phi(T_7)=\frac17,\quad
\Phi(T_8)=\frac{2}{17},\quad
\Phi(T_9)=\frac{7}{67},\quad
\Phi(T_{10})=\frac{4}{41},
]
but I am not ready to claim those as proved closed forms.

So the honest answer is: I do not currently have a trustworthy closed form for the conductance of (T_n). The papers I checked on triangular-grid isoperimetry and related triangular-grid pursuit/evasion define the graph and prove isoperimetric statements, but I did not find an explicit conductance formula there. ([arXiv][2])

The next useful step is to write the exact conductance minimization over the staircase family in WL form and see whether it collapses to a piecewise formula.

[1]: https://mathworld.wolfram.com/TriangularGridGraph.html?utm_source=chatgpt.com "Triangular Grid Graph -- from Wolfram MathWorld"
[2]: https://arxiv.org/html/2312.12110v1 "An Isoperimetric Inequality and Pursuit-Evasion Games on Triangular Grid Graphs"

TriangularHoneycombAcuteKnight

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

TriangularHoneycombBishop

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

TriangularHoneycombObtuseKnight

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

TriangularHoneycombQueen

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

TriangularHoneycombRook

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

TriangularSnake

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

TruncatedSquareLattice n×n

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

TruncatedSquareLattice m×n

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

Web

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

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

Wheel

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

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

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

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

}],{n,4,20}]

bug(473026): Poor (interpolating function) result fromFind GeneratingFunction[Table[(Floor[(2 (n - 1))/3] + 2)/(3 Floor[(2 (n - 1))/3]), {n, 4, 20}], x]

gf=(x^4)FindGeneratingFunction[seq,x]

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

bug(473025): Overly complicated Piecewise from FindSequenceFunction[Table[Piecewise[{{1/3, n == 3}}, 2/(3 Floor[n/2])], {n, 3, 25}], n - 2]

FindSequenceFunction[seq,n-3]

gf=x^4FindGeneratingFunction[seq,x]//Factor

ChatGPT 5.4 Heavy thinking 1

Plan: use the conductance definition with volume, split cuts according to whether they contain the hub, and optimize under the half-volume constraint.

Built-in conventions: `WheelGraph[n]` is the wheel on `n` vertices, i.e. one hub joined to every vertex of the cycle `C_(n - 1)`. `GraphData` lists `"Conductance"` as graph conductance, and MathWorld describes conductance as the normalized Cheeger quantity obtained by replacing `|S|` with `vol(S) = Sum_{v in S} deg(v)`. ([Wolfram Documentation Center][1])

Using
[
\Phi(G)=\min_{0<\mathrm{vol}(S)\le \mathrm{vol}(V)/2}\frac{|\partial S|}{\mathrm{vol}(S)},
]
the exact conductance of `{"Wheel", n}` for `n >= 4` is

[
\Phi(W_n)=\frac{m+2}{3m},
\qquad
m=\left\lfloor \frac{2n-2}{3}\right\rfloor.
]

Equivalently,

[
\Phi(W_n)=
\begin{cases}
\dfrac{2 n+3}{6 n-9}, & n \equiv 0 \pmod 3,\ n \ge 6,[6pt]
\dfrac{n+2}{3 n-3}, & n \equiv 1 \pmod 3,\ n \ge 4,[6pt]
\dfrac{n+1}{3 n-6}, & n \equiv 2 \pmod 3,\ n \ge 5.
\end{cases}
]

So the first values are
[
\frac23,\ \frac23,\ \frac59,\ \frac12,\ \frac12,\ \frac7{15},\ \frac49,\ \frac49,\ \frac37,\dots
]

Wolfram Language:

```wl
WheelConductance[n_Integer?Positive] :=
  Piecewise[
    {{(Floor[(2 n - 2)/3] + 2)/(3 Floor[(2 n - 2)/3]), n >= 4}},
    Missing["NotApplicable"]
  ]
```

or explicitly by residue class:

```wl
WheelConductance[n_Integer?Positive] :=
  Piecewise[
    {
      {(2 n + 3)/(6 n - 9), n >= 6 && Mod[n, 3] == 0},
      {(n + 2)/(3 n - 3), n >= 4 && Mod[n, 3] == 1},
      {(n + 1)/(3 n - 6), n >= 5 && Mod[n, 3] == 2}
    },
    Missing["NotApplicable"]
  ]
```

Proof. Let `h` be the hub.

1. `h notin S`.

Write `a = |S|`, since then `S` consists only of rim vertices, each of degree 3. Let `r >= 1` be the number of connected rim blocks of `S` on the cycle `C_(n-1)`. Then

* `vol(S) = 3 a`,
* `|\partial S| = a + 2 r`.

The `a` term comes from the spokes to the hub, and each rim block contributes 2 cycle edges to the boundary. Hence
[
\frac{|\partial S|}{\mathrm{vol}(S)}
====================================

\frac{a+2r}{3a}
\ge
\frac{a+2}{3a},
]
with equality exactly when `r = 1`, i.e. `S` is a single consecutive rim block.

The half-volume constraint is
[
3a \le \frac{1}{2}(4n-4)=2n-2,
]
so `a <= Floor[(2n-2)/3] = m`. Since `(a+2)/(3a)` decreases with `a`, the best set in this case is a consecutive rim block of length `m`, giving
[
\Phi_0=\frac{m+2}{3m}.
]

2. `h in S`.

Write `S = {h} union A`, with `a = |A|`. Let `r` be the number of rim blocks of `A` on `C_(n-1)`; for `a > 0`, we have `r >= 1`. Then

* `vol(S) = (n-1) + 3a`,
* `|\partial S| = (n-1-a) + 2r`.

So for `a > 0`,
[
\frac{|\partial S|}{\mathrm{vol}(S)}
\ge
\frac{n+1-a}{n-1+3a},
]
with equality when `A` is one consecutive rim block. The half-volume constraint gives
[
n-1+3a \le 2n-2,
\qquad\text{so}\qquad
a \le \left\lfloor\frac{n-1}{3}\right\rfloor.
]
Since `(n+1-a)/(n-1+3a)` decreases with `a`, the best set in this case is obtained at `a = Floor[(n-1)/3]`.

A residue-class check shows this best hub-containing value is always at least `Phi_0`, with equality only when `n == 1 mod 3`. Therefore the global minimum is always
[
\Phi(W_n)=\frac{m+2}{3m},
\qquad
m=\left\lfloor \frac{2n-2}{3}\right\rfloor.
]

The minimizers are:

* always: a consecutive rim block of length `Floor[(2n - 2)/3]`;
* additionally when `n == 1 mod 3`: the hub together with a consecutive rim block of length `(n - 1)/3`.

[1]: https://reference.wolfram.com/language/ref/WheelGraph.html?utm_source=chatgpt.com "WheelGraph - Wolfram Language Documentation"

ChatGPT 5.4 Heavy thinking 2

Plan: pick the shortest exact form, then note the best alternative only if you want an explicit residue-class version.

The simplest exact representation is

[
\Phi(W_n)=\frac{1}{3}\left(1+\frac{2}{\left\lfloor \frac{2n-2}{3}\right\rfloor}\right),
\qquad n\ge 4.
]

That is just your earlier formula rewritten slightly:
[
\frac{\lfloor(2n-2)/3\rfloor+2}{3\lfloor(2n-2)/3\rfloor}
========================================================

\frac13\left(1+\frac{2}{\lfloor(2n-2)/3\rfloor}\right).
]

For Wolfram Language, I would use exactly this:

```wl
WheelConductance[n_Integer?Positive] :=
  Piecewise[
    {{(1 + 2/Floor[(2 n - 2)/3])/3, n >= 4}},
    Missing["NotApplicable"]
  ]
```

I think this is the cleanest because:

* single branch;
* no `Mod`;
* the structure is transparent;
* it mirrors the Cheeger-constant form `1 + 2/Floor[n/2]`.

If you want the simplest prose form instead, I would write:

[
\Phi(W_n)=\frac{m+2}{3m},
\qquad
m=\left\lfloor \frac{2n-2}{3}\right\rfloor.
]

That is probably the neatest theorem-style statement.

If you want, I can also give the corresponding one-line proof in the same compact style.

WheelComplement

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

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

WhiteBishop n×n

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

WhiteCamel n×n

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

Zebra n×n

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