A large k-tree in graphs of bounded maximum degree and in star-free graphs

NEW

Problem: In Ozeki–Sugiyama’s terminology, a “$k$-tree” means a tree with at most $k$ leaves, not a chordal $k$-tree. Thus the problem is:

For integers $k\ge3,d,n$, determine

$$f_{k,d}(n)=\min_G \tau_k(G),$$

where $G$ ranges over all finite connected simple graphs of order $n$ and maximum degree at most $d$, and $\tau_k(G)$ is the maximum order of a subtree of $G$ with at most $k$ leaves.

Literal caveat: if $d=1,n>2$, no such connected graph exists, so the universal formulation is vacuous and has no finite largest value unless one imposes the standard nonempty-class convention. Below assume the class is nonempty.

Result: If $d\le2$, then

$$f_{k,d}(n)=n,$$

because every connected graph of maximum degree at most $2$ has a Hamilton path or is itself a path/cycle.

For $d\ge3$, the exact value is the following finite dynamic-programming quantity.

For $s\ge1$, call a tree $s$-good if every subtree with at most $k$ leaves has order at most $s$. Let $M_{k,d}(s)$ be the maximum order of an $s$-good tree of maximum degree at most $d$. Then

$$\boxed{f_{k,d}(n)=\min\{s:n\le M_{k,d}(s)\}.}$$

It remains to give $M_{k,d}(s)$ explicitly.

A rooted branch is a rooted tree which may later be attached to one parent, so every vertex has at most $d-1$ children. For a rooted branch $R$, define

$$\alpha_i(R)=\max |H|,$$

where $H$ ranges over subtrees of $R$ containing the root such that, after adding one external parent edge at the root, $H$ has at most $i$ leaves among its own vertices. Put

$$\alpha(R)=(\alpha_1(R),\dots,\alpha_k(R)).$$

For fixed $s$, profiles satisfy

$$1\le \alpha_i(R)\le 1+i(s-1),$$

because each such rooted subtree is the union of at most $i$ root-to-leaf paths, each of order at most $s$. Hence there are finitely many profiles.

Given child profiles $q^1,\dots,q^t$, define

$$\Phi_i(q^1,\dots,q^t) = \max\left\{1,\, 1+\sum_{r\in J}q^r_{a_r}: \varnothing\ne J\subseteq[t],\ a_r\in\{1,\dots,k\},\ \sum_{r\in J}a_r\le i \right\}.$$

This is the resulting rooted profile at the parent.

Also define the largest $k$-tree through the parent:

$$\Psi(q^1,\dots,q^t) = \max\left\{ 1,\, 1+q^r_a\ (1\le a\le k-1),\, 1+\sum_{r\in J}q^r_{a_r}\ (|J|\ge2,\ \sum a_r\le k) \right\}.$$

Now define $B_s(p)$ inductively on $p_1$: $B_s(p)$ is the maximum order of an $s$-good rooted branch of profile $p$, or $-\infty$ if none exists.

Base:

$$B_s(1,\dots,1)=1.$$

Induction:

$$B_s(p)= \max\left\{ 1+\sum_{r=1}^t B_s(q^r): 1\le t\le d-1,\ \Phi(q^1,\dots,q^t)=p,\ \Psi(q^1,\dots,q^t)\le s \right\}.$$

Only child profiles with finite $B_s$ are allowed.

Finally,

$$M_{k,d}(s)= \max\left\{ 1+\sum_{r=1}^t B_s(q^r): 0\le t\le d,\ \Psi(q^1,\dots,q^t)\le s \right\}.$$

This is finite and computable because the profile set is finite.

Proof of correctness: Every connected graph $G$ of maximum degree at most $d$ has a spanning tree $S$ with maximum degree at most $d$. Any $k$-tree in $S$ is also a $k$-tree in $G$. Hence the extremal problem reduces exactly to trees.

The recurrence for $B_s$ is forced by cutting a rooted branch at its root. A rooted subtree either consists only of the root, or chooses some child branches and distributes a leaf budget among them; this gives $\Phi$. A forbidden $k$-tree either lies wholly inside a child branch or passes through the root; the latter case is exactly measured by $\Psi$. Thus the recurrence characterizes precisely all $s$-good rooted branches.

Similarly, an unrooted $s$-good tree is obtained by choosing a root with at most $d$ rooted branches, and the condition that no $k$-tree through the root has order exceeding $s$ is exactly $\Psi\le s$. Hence the displayed formula gives $M_{k,d}(s)$.

Therefore, if $n>M_{k,d}(s-1)$, every $n$-vertex tree of maximum degree at most $d$ contains a $k$-tree of order at least $s$. Conversely, if $n\le M_{k,d}(s)$, an $s$-good extremal tree of order $M_{k,d}(s)$ contains a connected subtree of every smaller order $n$, obtained by repeatedly deleting leaves, so there is an $n$-vertex example with no $k$-tree larger than $s$. Thus

$$f_{k,d}(n)=\min\{s:n\le M_{k,d}(s)\}.$$

Audit: the proof uses only finite simple connected graphs, the paper’s $k$-ended-tree convention, and maximum-degree bound $d$. The only repair is excluding the empty class $d=1,n>2$. No stronger hypothesis is introduced.

Citation: No external resolution is used; the formula and proof above are self-contained.