For a graph G, a subset <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$S\subseteq V_G$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>S</mi> <mo>⊆</mo> <msub> <mi>V</mi> <mi>G</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> is generalized 4-independent if the induced subgraph G[S] contains no 4-vertex tree as a subgraph. A maximum generalized 4-independent set is one of maximum cardinality; its size is the generalized 4-independence number. A subcubic tree is a tree of maximum degree at most 3. In this paper, we first establish sharp lower and upper bounds on the generalized 4-independence number of a subcubic tree of order n and characterize all extremal trees attaining equality in both bounds. We further show that if T is a subcubic tree of order n with generalized 4-independence number <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\varphi $</EquationSource> <EquationSource Format="MATHML"><math> <mi>φ</mi> </math></EquationSource> </InlineEquation>, then the number <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\Phi (T)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Φ</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> of maximum generalized 4-independent sets satisfies <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\Phi (T)\le \lambda ^{6n-7\varphi +3},$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Φ</mi> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <msup> <mi>λ</mi> <mrow> <mn>6</mn> <mi>n</mi> <mo>-</mo> <mn>7</mn> <mi>φ</mi> <mo>+</mo> <mn>3</mn> </mrow> </msup> <mo>,</mo> </mrow> </math></EquationSource> </InlineEquation> where <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\lambda \thickapprox 1.3803$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>λ</mi> <mo>≈</mo> <mn>1.3803</mn> </mrow> </math></EquationSource> </InlineEquation> is the largest real root of <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$x^4-x^3-1=0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>x</mi> <mn>4</mn> </msup> <mo>-</mo> <msup> <mi>x</mi> <mn>3</mn> </msup> <mo>-</mo> <mn>1</mn> <mo>=</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>.

Maximum generalized 4-independent sets in subcubic trees

期刊论文
发表日期：

2026年2月3日

查看全文

Jing Huang,
Xuezhu Liao,
Lifang Zhao

摘要

For a graph G, a subset $S\subseteq V_G$ $S \subseteq V_{G}$ is generalized 4-independent if the induced subgraph G[S] contains no 4-vertex tree as a subgraph. A maximum generalized 4-independent set is one of maximum cardinality; its size is the generalized 4-independence number. A subcubic tree is a tree of maximum degree at most 3. In this paper, we first establish sharp lower and upper bounds on the generalized 4-independence number of a subcubic tree of order n and characterize all extremal trees attaining equality in both bounds. We further show that if T is a subcubic tree of order n with generalized 4-independence number $\varphi $ $φ$ , then the number $\Phi (T)$ $Φ (T)$ of maximum generalized 4-independent sets satisfies $\Phi (T)\le \lambda ^{6n-7\varphi +3},$ $Φ (T) \leq λ^{6 n - 7 φ + 3},$ where $\lambda \thickapprox 1.3803$ $λ \approx 1.3803$ is the largest real root of $x^4-x^3-1=0$ $x^{4} - x^{3} - 1 = 0$ .