Halin图独立集计数极值问题：从一般结构到三次正则图的理论与边界分析

《Discrete Optimization》：On the number of independent sets in Halin graphs

本综述聚焦于平面图论中Halin图的独立集计数问题，系统探讨了在顶点数n固定的前提下，如何刻画使独立集总数σ(G)达到极值的最大一般Halin图和最大三次Halin图，并提供了相关图类独立集数量的渐近下界。研究结合了图的变换技巧与极值图论方法，深化了对特定图类组合结构（如特征树T、伴随圈C）与独立集分布关系的理解，并为化学图论中的Merrifield–Simmons指数等研究提供了理论参考。

　　

亮点

从Halin图的结构来看，基于其特征树T，顶点集V(T)可以被划分为V(T)=V₀∪ V₁∪ V₂，其中V₀表示T的叶子集，也就是Halin图伴随圈上的顶点；V₁是T的支撑顶点集；V₂是T中剩余的顶点集（V₂可能为空）。任何在V(T) \ V₀中的顶点都是Halin图H的内部顶点。如果特征树T中的一个支撑顶点在H中仅与一个内部顶点相邻，则称其为“友好”支撑顶点；否则，若它与至少两个内部顶点相邻，则称其为“不良”支撑顶点。

最大三次Halin图

令CH_n表示顶点数为n的三次Halin图集合。显然，在CH_n中，n ≥ 4且为偶数。对于偶数n ≥ 6，我们记Cm_n为一种树，它通过给路径P_(n+2)/2的每个非叶子顶点连接一个悬挂顶点而得到。令A_n为顶点数为n、特征树为Cm_n的三次Halin图集合。一个梯子L_2k（k ≥ 1）就是笛卡尔积P_k□ P₂。假设CL_n∈ A_n是一个Halin图，它由L_n-2通过添加两个顶点u和v得到，u和v分别是……

渐近下界

在本节中，我们转而确定一般Halin图和三次Halin图的独立集数量的渐近下界的存在性。在展示主要结果之前，我们首先引入著名的Fekete引理，作为后续证明中的一个有用工具。一个（正）序列(u_i)_i=1^∞是次可加的（相应地，次可乘的），如果对于任意自然数m和n，有u_m+n≤ u_m+ u_n（相应地，u_m+n≤ u_mu_n）。

引理 4.1 [28]

如果(u_i)_i=1^∞是一个次可加序列，那么lim_n→∞u_n/n = inf_n∈Nu_n/n。

取v^*……

结论

在本文的第2节（最大一般Halin图）和第3节（最大三次Halin图）中，基于Halin图的结构，我们引入了若干图变换，包括FV变换、α-变换和β-变换，所有这些变换都增加了Halin图的独立集数量。通过使用这些图变换，我们确定了在所有顶点数为n的一般Halin图以及所有三次Halin图中，关于独立集数量达到最大的图。