Tree Depth

Author

Eric W. Weisstein
July 1, 2026

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

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

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

Table

DateString[]

table=GraphDataCountTable["TreeDepth",{"Alkane"->070941,"Andrasfai"->005843,"Antiprism"->394938,"Apollonian"->000027,"Barbell"->000027,"Book"->010709,"Centipede"->070941,"CocktailParty"->005408,"Complete"->000027,"CompleteBipartite"->000027,"CompleteTripartite"->005408,"CompleteTripartiteMinusPerfectMatching"->005408,"Crown"->326178,"Cycle"->070941,"CycleComplement"->326178,"DorogovtsevGoltsevMendes"->000027,"Empty"->000012,"Ladder"->329202,"LadderRung"->007395,"MoebiusLadder"->396686,"Path"->070939,"PathComplement"->028310,"Prism"->395540,"Star"->040000,"Sun"->000027,"TriangularHoneycombRook"->000027,"Wheel"->080800,"WheelComplement"->326178}]

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

Parametrized families

<<MathWorld`Graphs`

Alkane

A070941

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

Table[1+Ceiling[Log2[n+1]],{n,20}]

1+Ceiling[Log2[Range[20]+1]]

Codex 5.5 High

The n-alkane graph consists of a path of n spine vertices, with two pendant leaves attached to each spine vertex, together with one additional pendant endpoint at each end of the spine.  It contains the n-centipede tree as an induced subgraph by keeping the spine and one pendant leaf at each spine vertex, so td(Alkane_n) >= td(Centipede_n).  For the upper bound, take an optimal elimination forest for the spine path P_n and attach every alkane leaf as a child of its adjacent spine vertex; this increases the height by at most one and its closure contains all alkane edges.  Since td(P_n) = Ceiling[Log2[n + 1]], the tree-depth is 1 + Ceiling[Log2[n + 1]].

AlternatingGroupGraph

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

Andrasfai

A005843

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

ChatGPT 5.5 Pro Standard

## Plan

1. Rewrite your `CirculantGraph[3 n - 1, Range[1, 3 n, 3]]` convention as a clean modular edge rule.
2. Prove two structural lemmas:

   * (A_n) is (n)-vertex-connected.
   * In an (n)-connected graph, the top (n) labels in any vertex-ranking are forced to be unique.
3. Use induction: the top (n) singleton labels force two top labels into some cyclic block of three consecutive vertices; after moving the two largest labels there and rotating, deleting that block leaves an induced (A_{n-1}). This gives the missing lower bound.

This is essentially the Barrus–Sinkovic proof of their Theorem 4.3, rewritten in your convention and with the lower-bound mechanism made explicit. MathWorld gives the same Andrásfai/circulant convention, and Wolfram’s circulant convention is adjacency by the listed offsets and their negatives. ([MathWorld][1]) Barrus–Sinkovic state (\operatorname{td}(\operatorname{And}(k))=2k) and (\operatorname{td}(\operatorname{And}(k)-v)=2k-1). 

---

## Theorem

For every (n\ge 1),

[
\operatorname{td}(A_n)=2n,
]

where

[
A_n=\operatorname{CirculantGraph}(3n-1,{1,4,7,\ldots,3n-2}).
]

Moreover, for every vertex (v),

[
\operatorname{td}(A_n-v)=2n-1.
]

## Proof

Write

[
m_n=3n-1,\qquad V(A_n)=\mathbb Z_{m_n}.
]

Because

[
{1,4,\ldots,3n-2}
]

is closed under negation modulo (m_n), two distinct vertices (i,j\in\mathbb Z_{m_n}) are adjacent exactly when the ordinary positive difference between their representatives is congruent to (1\pmod 3). Equivalently, for (0\le i<j\le 3n-2),

[
ij\in E(A_n)\quad\Longleftrightarrow\quad j-i\equiv 1\pmod 3.
]

### Upper bound

Let

[
I={0,3,6,\ldots,3n-3}.
]

Then (|I|=n), and (I) is independent, since the difference between two vertices of (I) is divisible by (3), not congruent to (1\pmod 3).

Give every vertex of (I) label (1), and give the remaining (2n-1) vertices distinct labels (2,3,\ldots,2n). This is a feasible vertex-ranking: the only repeated label is (1), and any path between two distinct vertices of (I) must immediately leave (I), because (I) is independent; hence such a path has an internal vertex with label greater than (1). Therefore

[
\operatorname{td}(A_n)\le 2n.
]

### Lemma 1: (A_n) is (n)-connected

We prove the slightly stronger statement that between any two distinct vertices of (A_n) there are at least (n) internally vertex-disjoint paths.

For (n=1), (A_1=K_2), so this is clear.

Assume the claim for (A_j). Consider (A_{j+1}), whose vertices are

[
0,1,\ldots,3j+1.
]

The induced subgraph on

[
{0,1,\ldots,3j-2}
]

is exactly (A_j). Since (A_{j+1}) is vertex-transitive and has the reflection automorphism (x\mapsto -x), it suffices to consider two vertices (0) and (a) with

[
1\le a\le 3j-2.
]

By induction, inside the induced (A_j) there are (j) internally disjoint (0)-to-(a) paths.

Now consider the three new vertices

[
B={3j-1,3j,3j+1}.
]

The vertex (0) is adjacent to (3j+1), since (3j+1\equiv 1\pmod 3). Among the three consecutive vertices of (B), exactly one vertex (b) satisfies

[
b-a\equiv 1\pmod 3,
]

so (b) is adjacent to (a). Also, (B) induces a path, because consecutive vertices differ by (1). Hence there is a (0)-to-(a) path whose internal vertices all lie in (B). This path is internally disjoint from the previous (j) paths, which used only vertices of ({0,\ldots,3j-2}).

Thus (A_{j+1}) has (j+1) internally disjoint paths between any two vertices. By induction, (A_n) is (n)-connected.

### Lemma 2: top labels are unique in a highly connected graph

Let (G) be (q)-connected, and let (r) be a feasible vertex-ranking of (G). Then the (q) largest labels appearing in (r) each occur exactly once.

Proof. The largest label is unique, since (G) is connected and there is no higher label to separate two vertices with the largest label. Now argue downward. Suppose the (s-1) labels larger than a label (\ell) are already known to be unique, with (s\le q). If (\ell) appeared on two vertices (x,y), then (q)-connectivity gives (q) internally disjoint (x)-to-(y) paths. Each such path must contain an internal vertex with label greater than (\ell). But there are only (s-1<q) such higher-labeled vertices, since those higher labels are unique. Contradiction. Therefore (\ell) is unique. This proves the claim for the top (q) labels.

### Lower bound by induction

We prove

[
\operatorname{td}(A_n)\ge 2n
]

by induction on (n).

For (n=1), (A_1=K_2), so (\operatorname{td}(A_1)=2).

Assume (n\ge 2) and

[
\operatorname{td}(A_{n-1})=2n-2.
]

Let (r) be an optimal ranking of (A_n), using (t) labels. Since (A_n) contains an induced copy of (A_{n-1}), namely the subgraph on

[
{0,1,\ldots,3n-5},
]

we already know

[
t\ge 2n-2\ge n.
]

By Lemma 1, (A_n) is (n)-connected. Hence, by Lemma 2, the top (n) labels in (r) occur on (n) distinct vertices.

Mark those (n) vertices on the cyclic order of the (3n-1) vertices. Some three consecutive vertices must contain at least two marked vertices. Indeed, if every three consecutive cyclic vertices contained at most one marked vertex, then the cyclic distance between marked vertices would always be at least (3), forcing at least (3n) vertices on the cycle, but (A_n) has only (3n-1) vertices.

Thus there is a cyclic block of three consecutive vertices containing two vertices whose labels are among the top (n) labels. Since the top (n) labels are all unique and are larger than every repeated label, we may permute the top (n) labels among their (n) vertices without destroying feasibility: any path condition involving a repeated label only needs some larger internal label, and every top-(n) label is still larger than every repeated label. Therefore we may assume that the two largest labels (t-1,t) occur in that block.

Using the cyclic automorphism of (A_n), rotate the graph so that this block is

[
B={3n-4,3n-3,3n-2}.
]

Then the remaining vertices

[
{0,1,\ldots,3n-5}
]

induce (A_{n-1}). The restriction of (r) to this induced (A_{n-1}) is still a feasible ranking, so it must use at least

[
\operatorname{td}(A_{n-1})=2n-2
]

distinct labels. The two largest labels (t-1,t) are on (B), not on this induced (A_{n-1}). Hence the whole ranking uses at least

[
(2n-2)+2=2n
]

distinct labels. Therefore

[
\operatorname{td}(A_n)\ge 2n.
]

Together with the upper bound,

[
\operatorname{td}(A_n)=2n.
]

### Vertex-deleted graph

Since (A_n) is connected and vertex-transitive, all graphs (A_n-v) are isomorphic. The standard recursive characterization of tree-depth for a connected graph gives

[
\operatorname{td}(G)=1+\min_{v\in V(G)}\operatorname{td}(G-v).
]

Thus, writing (T=\operatorname{td}(A_n-v)), vertex-transitivity gives

[
2n=\operatorname{td}(A_n)=1+T,
]

so

[
\operatorname{td}(A_n-v)=2n-1.
]

This also explicitly rules out (\operatorname{td}(A_n)=2n-1).

---

For a notebook, the upper-bound ranking can be represented on the (0)-based vertex set as:

```wl
upperRanking[n_Integer?Positive] := Module[
  {verts, indep, rest},
  verts = Range[0, 3 n - 2];
  indep = Range[0, 3 n - 3, 3];
  rest = Complement[verts, indep];
  Association[Join[Thread[indep -> 1], Thread[rest -> Range[2, 2 n]]]]
]
```

[1]: https://mathworld.wolfram.com/AndrasfaiGraph.html "Andrásfai Graph -- from Wolfram MathWorld"

Codex 5.5 High

Write the n-Andrasfai graph as the circulant graph on Z/(3 n - 1)Z in which two vertices are adjacent exactly when their positive cyclic difference is congruent to 1 modulo 3.  The vertices 0,3,6,...,3 n - 3 form an independent set of size n, so coloring these vertices 1 and all remaining vertices with distinct colors 2 through 2 n gives td(A_n) <= 2 n.  For the lower bound, first note that A_n is n-connected.  This follows by induction: A_{j+1} contains an induced A_j on vertices 0,...,3 j - 2, and the three new consecutive vertices 3 j - 1,3 j,3 j + 1 give one additional internally disjoint path between any two old vertices; vertex transitivity and reflection then handle all vertex pairs.  In any n-connected graph, the n largest labels in a vertex ranking are unique, since two vertices with the same kth-largest label would require n internally disjoint paths, each containing one of the fewer than n higher-labeled vertices.  Now take a ranking of A_n.  Among the n vertices carrying the n largest labels, two lie in some three consecutive cyclic positions, since otherwise n marked vertices would require at least 3 n cyclic positions.  Permuting the n largest labels among their vertices preserves feasibility, so put the two largest labels in such a three-vertex block and rotate the graph so that the block is the last three vertices.  The remaining vertices induce A_{n-1}; by induction their restriction needs at least 2 n - 2 labels, and the two largest labels are outside this induced subgraph.  Hence any ranking uses at least 2 n labels.  Therefore td(A_n) = 2 n.

Antelope n×n

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

Antelope m×n

DeleteCases[
Flatten[Table[{
{m,n},
GraphData[{"Antelope",{m,n}},"TreeDepth"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}
]//Quiet

Antiprism

A394938

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

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

Table[Floor[Log2[2 n-1]]+Floor[Log2[2 n-1-(2^(Floor[Log2[2 n-2]]-1))]]+2,{n,3,25}]

ChatGPT 5.5 Pro

Let R(m) = Floor[Log2[m + 1]] + Floor[Log2[m + 1 - 2^(Floor[Log2[m]] - 1)]] + 1.  The n-antiprism graph is isomorphic to the square of the cycle C_{2 n}.  Ortiz, Zemke, King, Narayan, and Hornak prove that the rank number of P_2 x C_n is R(n - 2) + 2 for n >= 4, and that for even n >= 4, the rank number of C_n^2 is one less than the rank number of P_2 x C_n.  Since tree-depth is the vertex-ranking number, applying this with cycle length 2 n gives td(Antiprism_n) = R(2 n - 2) + 1 for n >= 3.  The case n = 3 is included, since R(4) + 1 = 5.

Codex 5.5 High

The exact formula is logarithmic through the ladder-ranking function R.  The local constructor check AntiprismGraphQ identifies the n-antiprism graph with CirculantGraph[2 n,{1,2}], i.e. C_{2 n}^2, so the even cycle-square theorem applies directly.

Apollonian

A000027

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

Table[n+3,{n,6}]

ChatGPT 5.5 Pro

For the Apollonian graph A_n, use the recursive construction from the initial K_4 with outer triangle a,b,c and interior vertex d.  Let I_n be the part strictly inside the outer triangle.  The upper bound td(A_n) <= n + 3 is obtained by putting a,b,c on top of an elimination forest for I_n; inside I_n, put d at the root and attach the three recursively filled subtriangles, each of height n - 1, below it.  For the lower bound, prove by induction the stronger deletion lemma: if K is the initial K_4 and nonempty S is a subset of K with |S| <= 3, then td(A_n - S) >= n + 3 - |S|.  The base case is K_4.  For the induction step, after any additional vertex deletion, one first-level copy of A_{n-1} remains with at most the corresponding number of boundary vertices deleted, so the induction hypothesis gives the required lower bound.  Applying the connected-graph recurrence to A_n then gives td(A_n) >= n + 3.  Hence td(A_n) = n + 3 for n >= 1.

Codex 5.5 High

The proof uses the actual combinatorial ApollonianGraph construction in MathWorld`Graphs`: A_1 is K_4 and each subsequent level inserts one vertex in every current triangular face adjacent to the three face vertices.  After deleting the first interior vertex, the remaining interiors split into three smaller copies below the fixed outer triangle, giving the upper bound; the deletion lemma supplies the matching lower bound.

Barbell

A000027

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

Codex 5.5 High

Let B_n be the barbell graph formed from two n-cliques joined by one bridge edge.  The connected-graph recurrence for tree-depth is td(G) = 1 + Min_v Max td(C), where C ranges over the components of G - v.  Deleting a bridge endpoint leaves components K_{n-1} and K_n, so td(B_n) <= n + 1.  Conversely, if v is a bridge endpoint, G - v has a K_n component, while if v is not a bridge endpoint, G - v is connected and still contains the opposite K_n.  In every case the maximum remaining tree-depth is at least n, so td(B_n) = n + 1.

Bishop n×n

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

Bishop m×n

Entity["Graph",{"Bishop",{m,n}}]["TreeDepth"]

DeleteCases[
Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"TreeDepth"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

BlackBishop n×n

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

BlackBishop m×n

Entity["Graph",{"Bishop",{m,n}}]["TreeDepth"]

DeleteCases[
Flatten[Table[{
{m,n},
GraphData[{"BlackBishop",{m,n}},"TreeDepth"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}
]//Quiet

Book

A010709

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

Codex 5.5 High

The book graph here is the graph of n squares sharing one common edge.  For n = 1 this is C_4, whose tree-depth is 3.  For n >= 2, root the two common-edge vertices and then root one endpoint of each remaining page edge below them; this gives height 4.  The lower bound follows already from the two-page book, the domino graph: deleting any vertex from the domino graph leaves a graph containing P_4, whose tree-depth is 3, so the connected-graph recurrence gives tree-depth at least 4.  Thus the tree-depth is Min[n + 2, 4].

Bruhat

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

Camel n×n

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

Camel m×n

Entity["Graph",{"Camel",{m,n}}]["TreeDepth"]

DeleteCases[
Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"TreeDepth"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Cameron

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

Centipede

A070941

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

Table[1+Ceiling[Log2[n+1]],{n,10}]

Codex 5.5 High

The n-centipede tree is obtained from the path P_n by attaching one pendant leaf to every path vertex.  More generally, if W(G) is obtained from a graph G by attaching one pendant leaf to every vertex, then td(W(G)) = td(G) + 1.  The upper bound attaches each new leaf below its neighbor in an optimal elimination forest for G.  For the lower bound, let r be any k-ranking of W(G).  For each original vertex v with pendant leaf v', define r'(v) = Max[r(v), r(v')] - 1.  If two vertices x and y of G had r'(x) = r'(y) and a path between them whose internal vertices all had r' at most that value, then choosing from each pair {x,x'} and {y,y'} a vertex with rank r'(x) + 1 gives a same-ranked path in W(G) with no larger internal rank, contradicting that r is a ranking.  Thus r' is a (k - 1)-ranking of G.  Applying this to G = P_n and using td(P_n) = Ceiling[Log2[n + 1]] gives td(Centipede_n) = 1 + Ceiling[Log2[n + 1]].

CocktailParty

A005408

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

Table[2n-1,{n,20}]

Codex 5.5 High

The n-cocktail party graph is the complete multipartite graph with n parts of size 2.  More generally, the tree-depth of a complete multipartite graph with N vertices and largest part size M is N - M + 1.  In a vertex ranking, adjacent vertices have distinct colors, so a repeated color can occur only inside one part.  If a color is repeated inside one part, every vertex outside that part lies on a two-edge path between same-colored vertices, so all outside vertices must have larger, mutually distinct colors.  Hence at least N - M + 1 colors are needed.  Conversely, color every vertex in a largest part with color 1 and color all remaining vertices with distinct colors 2 through N - M + 1.  For N = 2 n and M = 2 this gives td = 2 n - 1.

Complete

A000027

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

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

Codex 5.5 High

The complete graph K_n has a clique on n vertices, so any vertex ranking needs n distinct colors.  A chain of n vertices gives an elimination tree of height n whose closure contains K_n.  Hence td(K_n) = n.

CompleteBipartite n×n

A000027

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

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

Codex 5.5 High

For K_{n,n}, the complete multipartite formula with N = 2 n and largest part size M = n gives td(K_{n,n}) = N - M + 1 = n + 1.  Equivalently, color one part with color 1 and the other part with distinct colors 2 through n + 1 for the upper bound; any repeated color must lie in one part, and every vertex of the other part lies on a two-edge path between equal-colored vertices, forcing the n larger distinct colors.

CompleteBipartite m×n

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

DeleteCases[
Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"TreeDepth"],
1+Min[m,n]
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Codex 5.5 High

For K_{m,n}, the complete multipartite formula gives td(K_{m,n}) = m + n - Max[m,n] + 1 = Min[m,n] + 1.  The upper bound colors every vertex in a larger part with color 1 and gives distinct larger colors to the other part.  For the lower bound, any repeated color can occur only inside one part; if two vertices in that part share a color, every vertex in the opposite part lies on a two-edge path between them and must have a larger distinct color.

CompleteTripartite n×n×n

A005408

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

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

Codex 5.5 High

This is the complete tripartite graph with three parts of size n.  More generally, the tree-depth of a complete multipartite graph with N vertices and largest part size M is N - M + 1.  In a vertex ranking, adjacent vertices must have distinct colors, so any color that is repeated can occur only inside one part.  If a color is repeated inside one part, then every vertex outside that part lies on a two-edge path between same-colored vertices, so all outside vertices must have larger, mutually distinct colors.  Hence at least N - M + 1 colors are needed.  Conversely, color every vertex in a largest part with color 1 and color all remaining vertices with distinct colors 2 through N - M + 1.  Every path between same-colored vertices then has an internal vertex with larger color.  For parts n,n,n this gives 3 n - n + 1 = 2 n + 1.

CompleteTripartite k×m×n

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

DeleteCases[
Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"TreeDepth"],
k+m+n-Max[k,m,n]+1
},{n,10},{m,n},{k,m}],2],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Codex 5.5 High

For the complete tripartite graph with part sizes k, m, and n, apply the complete multipartite ranking argument.  With N = k + m + n and M = Max[k,m,n], at most one part can contain a repeated color in any vertex ranking, and all vertices outside that part must have distinct larger colors.  This gives the lower bound N - M + 1.  Coloring all vertices in a largest part with color 1 and giving distinct colors to the remaining N - M vertices attains the bound, so the tree-depth is k + m + n - Max[k,m,n] + 1.

CompleteTripartiteMinusPerfectMatching

A005408

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

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

Codex 5.5 High

Let the three parts all have size n, with the deleted edges forming a perfect matching.  The graph is a subgraph of K_{n,n,n}, so the complete multipartite formula gives the upper bound td <= 2 n + 1.  For the lower bound, first note the graph is (2 n - 1)-connected: its minimum degree is 2 n - 1, and deleting fewer than 2 n - 1 vertices leaves more than n + 1 vertices, hence vertices in at least two parts; the remaining cross-part adjacencies, with only matching edges missing, keep the graph connected.  A noncomplete k-connected graph has tree-depth at least k + 2, by repeatedly applying the connected-graph recurrence through the first k - 1 root deletions, after which a connected graph with at least two vertices remains.  With k = 2 n - 1, this gives td >= 2 n + 1, so the tree-depth is 2 n + 1.

CossidentePenttila

{
#,
q=GraphData[#,"NotationRules","CossidentePenttila"],
XXX,
GraphData[#,"TreeDepth"]
}&/@GraphData["CossidentePenttila"]

CrossedPrism

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

ChatGPT 5.5 Pro

No exact all-parameter tree-depth formula is established here.  What is safe is a logarithmic structural upper bound.  For even n = 2 m, group the crossed prism vertices into four-vertex blocks Q_j = {a_{2 j - 1}, a_{2 j}, b_{2 j - 1}, b_{2 j}}.  Each block induces a 4-cycle, and consecutive blocks are connected only by the two cycle edges between the corresponding a- and b-rings.  Deleting one block turns the cyclic chain into a linear chain; recursively deleting a middle block in a linear chain leaves two chains of at most half the size.  Ranking the four deleted vertices with the four largest labels gives U(t) <= 4 + U[Ceiling[(t - 1)/2]], so td(CrossedPrism_{2 m}) <= 4 + 4 Ceiling[Log2[m]].  Thus the crossed-prism tree-depth is O(log m), and any linear formula inferred from the small values is false.

Codex 5.5 High

This is recorded as an upper-bound result only.  The stored exact values 5,7,7,8 for parameters 4,6,8,10 do not determine a reliable closed form, and no lower-bound theorem has been supplied that would certify an exact crossed-prism formula.

Crown

A326178

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

Table[({{\[Piecewise], ({{1, n==1}, {2, n==2}, {n+1, True}})}}),{n,20}]

Codex 5.5 High

Let C_n be the n-crown graph, K_{n,n} with one perfect matching removed.  The cases n = 1 and n = 2 have tree-depths 1 and 2.  For n >= 3, the upper bound td(C_n) <= n + 1 follows because C_n is a subgraph of K_{n,n}, whose tree-depth is n + 1.  For the lower bound, C_3 is a 6-cycle and has tree-depth 4.  If n >= 4 and v is any vertex of C_n, then C_n - v contains an induced copy of C_{n-1}: delete v and ignore its matched nonneighbor.  The connected-graph recurrence therefore gives td(C_n) >= 1 + td(C_{n-1}).  Induction from C_3 gives td(C_n) >= n + 1, so td(C_n) = n + 1 for n >= 3.

CubeConnectedCycle

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

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

Cycle

A070941

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

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

Table[1+Ceiling[Log2[n]],{n,3,30}]

Table[1+IntegerLength[n-1,2],{n,3,30}]

Codex 5.5 High

For n >= 3, deleting any vertex of the cycle graph gives the path graph P_{n-1}.  The connected-graph recurrence for tree-depth gives td(C_n) >= 1 + td(P_{n-1}), since the root of any elimination tree leaves an elimination forest for C_n with one vertex removed.  Conversely, root an elimination tree at any cycle vertex and use an optimal elimination tree for the remaining path P_{n-1}.  Since td(P_r) = Ceiling[Log[2,r+1]], this gives td(C_n) = 1 + Ceiling[Log[2,n]], equivalently 1 + IntegerLength[n - 1,2].

CycleComplement

A326178

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

Table[Piecewise[{{n-2,n<=4}},n-1],{n,3,20}]

Codex 5.5 High

For n >= 5, the complement of C_n is noncomplete and has vertex connectivity n - 3.  The general lower bound td(G) >= k + 2 for a noncomplete k-connected graph therefore gives td >= n - 1.  For the matching upper bound, give the two endpoints of one deleted cycle edge color 1 and give all other vertices distinct colors 2 through n - 1.  The only repeated color is on a nonedge of the complement, and every path between those two vertices has an internal vertex with larger color.  Thus td(complement C_n) = n - 1 for n >= 5.  The small cases are the empty graph on 3 vertices and the matching 2 K_2, with tree-depths 1 and 2 respectively, giving Piecewise[{{n - 2, n <= 4}}, n - 1].

DiagonalIntersection

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

Dipyramid

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

DorogovtsevGoltsevMendes

A000027

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

Codex 5.5 High

Let D_n be the nth Dorogovtsev-Goltsev-Mendes graph in the MathWorld convention, so D_0 is K_2 and D_{n+1} is obtained from D_n by adding, for every old edge uv, a new vertex adjacent to u and v while retaining uv.  For the upper bound, start with an elimination forest for D_n.  Since every old edge uv has comparable endpoints in the forest, attach the new vertex for uv as a child of the deeper endpoint.  The new vertex is then comparable with both u and v, so the closure contains both new edges, and the height increases by at most one.  Since td(D_0) = 2, this gives td(D_n) <= n + 2.  For the lower bound, D_n for n >= 1 is the union of three copies of D_{n-1} arranged around the three sides of the initial triangle; the copies pairwise meet in one corner vertex and have empty triple intersection.  By induction, each copy has tree-depth n + 1.  If D_n had a vertex ranking using only n + 1 colors, then each copy would have to use all n + 1 colors.  In a connected graph, the largest color in a vertex ranking is unique, since two vertices with the largest color are joined by a path with no larger internal vertex.  Thus the unique largest-color vertex of D_n would have to lie in all three copies, contradicting the empty triple intersection.  Hence td(D_n) >= n + 2, and td(D_n) = n + 2.

DoubleCone

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

Empty

A000012

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

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

Codex 5.5 High

For n >= 1, the empty graph has no edges, so a rooted forest of height 1 with all vertices as roots has closure containing the graph.  A nonempty graph cannot have tree-depth 0, hence the tree-depth is 1.

ErectedPolygon

DeleteCases[Module[{n,r},
{
#,
{n,r}=GraphData[#,"NotationRules","ErectedPolygon"],
XXX,
GraphData[#,"TreeDepth"]
}
]&/@GraphData["ErectedPolygon"],
{__,x_,x_}]

FibonacciCube

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

Fiveleaper n×n

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

Fiveleaper m×n

Entity["Graph",{"Fiveleaper",{m,n}}]["TreeDepth"]

DeleteCases[
Flatten[Table[{
{m,n},
GraphData[{"Fiveleaper",{m,n}},"TreeDepth"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Flower

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

FoldedCube

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

Gear

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

Giraffe n×n

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

Giraffe m×n

Entity["Graph",{"Fiveleaper",{m,n}}]["TreeDepth"]

DeleteCases[
Flatten[Table[{
{m,n},
GraphData[{"Giraffe",{m,n}},"TreeDepth"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Goldberg

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

Grid n×n

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

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

Grid m×n

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

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"TreeDepth"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Grid n×n×n

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

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

Grid k×m×n

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

Sort@DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"TreeDepth"],
XXX
},{n,10},{m,n},{k,m}],2],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

HalvedCube

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

Hanoi

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

Helm

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

Hypercube

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

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

KC

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"KC",{m,n}},"TreeDepth"],
XXX
},{n,3,10},{m,10}],1],{_,x_,x_}]

Keller

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

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

King n×n

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

King m×n

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"King",{m,n}},"TreeDepth"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Knight n×n

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

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

Knight m×n

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

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"King",{m,n}},"TreeDepth"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

KP

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"KP",{m,n}},"TreeDepth"],
XXX
},{n,10},{m,10}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Ladder

A329202

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

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

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

ChatGPT 5.5 Pro Standard

Novotny, Ortiz, and Narayan prove the rank-number recurrence for the ladder graph L_n = P_2 x P_n: r(L_1) = 2, r(L_2) = 3, and, for n >= 3, r(L_n) = 2 + r(L_Floor[(n - 1)/2]).  The upper bound ranks the middle rung above recursively ranked halves, and the lower bound is their ladder lower-bound lemma.  Since rank number is tree-depth, solving the recurrence gives td(L_n) = Floor[Log2[n + 1]] + Floor[Log2[2 (n + 1)/3]] + 1 for n >= 1.

Codex 5.5 Pro

The formula is logarithmic and simplifies to Floor[2 Log2[n + 1]], so the sequence is OEIS A329202 with index shifted by one.  The apparent match with OEIS A027434 from the first nine terms is only a false prefix match and should not be linked.

LadderRung

A007395

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

Codex 5.5 High

The n-ladder-rung graph is a matching with n independent edges.  It has at least one edge, so its tree-depth is at least 2.  Root each edge at one endpoint and place its other endpoint below it; the resulting elimination forest has height 2 and its closure contains the matching.  Hence td(LadderRung_n) = 2.

LindgrenSousselier

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

LucasCube

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

MengerSponge

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

MoebiusLadder

A396686

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

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

Table[({{\[Piecewise], ({{4, n==3}, {Floor[Log2[n]]+Floor[Log2[((2 n)/3)]]+3, True}})}}),{n,3,25}]

ChatGPT 5.5 Pro Standard

With the MathWorld indexing, the n-Moebius ladder has 2 n vertices.  Alpert's recursive rank-number result gives td(M_3) = 4 and, for n >= 4, td(M_n) = 2 + td(L_{n - 1}).  Substituting the ladder formula gives td(M_n) = Floor[Log2[n]] + Floor[Log2[2 n/3]] + 3 for n >= 4.

Codex 5.5 Pro

The special case n = 3 is essential: the closed form for n >= 4 would give 5 there, while the triangular-prism-like smallest Moebius ladder has tree-depth 4.  OEIS A396686 records the general-term sequence Floor[2 Log2[n]] + 2, which agrees with the tree-depth of the n-Moebius ladder graph for n >= 4.

Mycielski

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

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

Necklace

seq=Table[GraphData[{"Necklace",n},"TreeDepth"],{n,10}]

Odd

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

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

Paley

{
#,
q=GraphData[#,"NotationRules","Paley"],
XXX,
GraphData[#,"TreeDepth"]
}&/@GraphData["Paley"]

Pan

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

Path

A070939

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

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

Table[Ceiling[Log2[n+1]],{n,50}]

bug(411251): FullSimplify[Ceiling[Log2[n + 1]] - (1 + Floor[Log2[n]]), n ∈ Integers && n > 0] could return 0

$Version

Subtract@@@Table[{Ceiling[Log2[n+1]],(1+Floor[Log2[n]])},{n,10^5}]//Union//Timing

Plot[Ceiling[Log2[n+1]]-(1+Floor[Log2[n]]),{n,.1,20}]

DiscretePlot[Ceiling[Log2[n+1]]-(1+Floor[Log2[n]]),{n,20}]

FullSimplify[Ceiling[Log2[n+1]]-(1+Floor[Log2[n]]),n∈Integers&&n>0]

Refine[Ceiling[Log2[n+1]]-(1+Floor[Log2[n]]),n∈Integers&&n>0]

FunctionExpand[Ceiling[Log2[n+1]]-(1+Floor[Log2[n]])]

Codex 5.5 High

Let f(n) be the tree-depth of the path graph P_n.  The connected-graph recurrence gives f(n) = 1 + Min_i Max[f(i - 1), f(n - i)], with f(0) = 0, since deleting the root vertex i leaves two path components.  The optimal choice is a middle vertex, and induction gives f(n) as the least h with n <= 2^h - 1.  Equivalently, f(n) = Ceiling[Log[2,n + 1]] = IntegerLength[n,2].

PathComplement

A028310

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

Table[({{\[Piecewise], ({{1, n≤2}, {n-1, True}})}}),{n,20}]

Codex 5.5 High

For n = 1 and n = 2, the complement of P_n is empty, so its tree-depth is 1.  For n >= 4, the complement of P_n is noncomplete and has vertex connectivity n - 3: its minimum degree is n - 3, and deleting fewer than n - 3 vertices leaves a connected complement because any remaining path-nonadjacent pair has a short connection through the remaining vertices.  The general lower bound td(G) >= k + 2 for a noncomplete k-connected graph gives td >= n - 1.  For the matching upper bound, give the two endpoints of one path edge color 1 and give all other vertices distinct colors 2 through n - 1.  The only repeated color is on a nonedge of the complement, and every path between the repeated-color vertices has an internal vertex with larger color.  The case n = 3 is an edge plus an isolated vertex, with tree-depth 2.  Thus td(complement P_n) = Piecewise[{{1, n <= 2}}, n - 1].

Peisert

{
#,
q=GraphData[#,"NotationRules","Peisert"],
XXX,
GraphData[#,"TreeDepth"]
}&/@GraphData["Peisert"]

Pell

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

PlummerToft

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

Prism

A395540

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

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

Table[If[n==3,5,Floor[Log2[n-1]]+Floor[Log2[n-1-(2^(Floor[Log2[n-2]]-1))]]+3],{n,3,25}]

ChatGPT 5.5 Pro

Let R(m) = Floor[Log2[m + 1]] + Floor[Log2[m + 1 - 2^(Floor[Log2[m]] - 1)]] + 1.  Ortiz, Zemke, King, Narayan, and Hornak prove that the rank number of the ladder graph P_2 x P_m is R(m), and that for n >= 4 the prism graph P_2 x C_n has rank number R(n - 2) + 2; the triangular prism has rank number 5.  Because tree-depth equals vertex-ranking number, td(Prism_n) = 5 for n = 3, and td(Prism_n) = R(n - 2) + 2 for n >= 4.

Codex 5.5 High

The local PrismGraph[n] is P_2 x C_n, and the cited ranking theorem proves the exact logarithmic formula.  In particular Prism_10 has tree-depth 8.

Queen n×n

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

Queen m×n

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Queen",{m,n}},"TreeDepth"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Rook n×n

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

Rook m×n

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Rook",{m,n}},"TreeDepth"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

RookComplement n×n

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

RookComplement m×n

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"RookComplement",{m,n}},"TreeDepth"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

SierpinskiCarpet

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

SierpinskiGasket

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

SierpinskiTetrahedron

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

Spoke n×n

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

StackedBook n×n

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

StackedBook m×n

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

StackedPrism n×n

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

StackedPrism m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"StackedPrism",{m,n}},"TreeDepth"],
XXX
},{m,3,8},{n,5}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Star

A040000

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

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

Codex 5.5 High

The one-vertex star has tree-depth 1.  For n >= 2, the star graph has an edge, so its tree-depth is at least 2.  Rooting the elimination tree at the center and putting all leaves below it gives height 2, so the tree-depth is 2 for all nontrivial stars.

Sun

A000027

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

Codex 5.5 High

In the n-sun graph, the n central vertices form a clique, and each outer vertex is adjacent to two consecutive clique vertices.  For the upper bound, put the clique vertices on one root-to-leaf chain and attach each outer vertex as a child of the deeper of its two clique neighbors; this has height n + 1.  For the lower bound, in any rooted forest whose closure contains the graph, the n clique vertices must lie on one chain.  Let c be the deepest clique vertex.  It has an outer neighbor s.  Since s is adjacent to c, the two vertices must be comparable in the forest.  If s is above c or below c, the root-to-leaf path containing c and s also contains all n clique vertices, so its height is at least n + 1.  Therefore the tree-depth is n + 1.

Sunlet

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

Tetrahedral

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

TorusGrid n×n

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

TorusGrid m×n

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"TorusGrid",{m,n}},"TreeDepth"],
XXX
},{n,3,20},{m,3,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Transposition

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

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

Trapezohedron

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

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

Triangular

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

TriangularGrid

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

TriangularHoneycombAcuteKnight

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

ChatGPT 5.5 Pro Standard

No proved all-parameter tree-depth formula is established here.  In the standard acute-knight coordinate model on vertices (i,j) with i,j >= 0 and i + j <= n - 1, using move differences (1,1), (2,-1), and (-1,2) and their negatives, the exact tree-depth recurrence gives values 1,1,2,3,3,4,5,6,7,8 for n = 1,...,10.  In particular, the tempting formula Floor[(2 n + 1)/3] is false at n = 8, where the tree-depth is 6.  The evidence suggests td(A_n) = n - 2 for n >= 5, but that remains a conjecture without a matching lower-bound proof.

Codex 5.5 Pro

The safe update is finite: record the exact computed values through n = 10 and do not add a GraphDataEntity all-n formula.  The graph splits by i - j modulo 3, and known triangular-grid ranking bounds support only td(A_n) = Theta(n) without an exact closed form.

TriangularHoneycombBishop

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

TriangularHoneycombObtuseKnight

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

TriangularHoneycombQueen

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

TriangularHoneycombRook

A000027

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

Table[n,{n,20}]

Codex 5.5 High

In the MathWorld constructor for the n-triangular honeycomb rook graph, the vertices are arranged in rows of sizes 1,2,...,n, and edges are added exactly between pairs of vertices in the same row.  Thus the graph is the disjoint union K_1 ⋃ K_2 ⋃ ... ⋃ K_n.  Tree-depth of a disjoint union is the maximum tree-depth of its connected components, and td(K_j) = j.  Therefore td(TriangularHoneycombRook_n) = Max[1,2,...,n] = n.

TriangularSnake

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

TruncatedSquareLattice n×n

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

TruncatedSquareLattice m×n

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"TruncatedSquareLattice",{m,n}},"TreeDepth"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Web

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

Wheel

A080800

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

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

Table[2+Ceiling[Log[2,n-1]],{n,4,20}]

Codex 5.5 High

The wheel graph W_n is the join of a single universal hub vertex with the cycle C_{n-1}.  For any graph G, adding a universal vertex increases tree-depth by exactly 1: put the universal vertex at the root for the upper bound, and in any elimination tree it is comparable with every vertex, so moving it to the root leaves an elimination forest for G of one smaller height.  Therefore td(W_n) = 1 + td(C_{n-1}) = 2 + Ceiling[Log[2,n - 1]], equivalently 2 + IntegerLength[n - 2,2].

WheelComplement

A326178

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

Table[n,{n,20}]

Codex 5.5 High

The n-wheel graph is the join of one hub vertex with the cycle C_{n-1}.  Taking complements turns this into the disjoint union of an isolated vertex and the complement of C_{n-1}.  Tree-depth of a disjoint union is the maximum tree-depth of its components, so td(complement W_n) = Max[1, td(complement C_{n-1})].  Using the cycle-complement formula gives td(complement W_4) = 1, td(complement W_5) = 2, and td(complement W_n) = n - 2 for n >= 6.  Equivalently, td(WheelComplement_n) = Piecewise[{{1, n == 4}, {2, n == 5}}, n - 2].

WhiteBishop n×n

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

WhiteBishop m×n

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"WhiteBishop",{m,n}},"TreeDepth"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

WhiteCamel n×n

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

Zebra n×n

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

Zebra m×n

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Zebra",{m,n}},"TreeDepth"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet