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

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

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

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

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

For fixed $s$, profiles satisfy

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

This is the resulting rooted profile at the parent.

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

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:

Induction:

Only child profiles with finite $B_s$ are allowed.

Finally,

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

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.