提出2-树在双色三角约束下的精确计数公式，可用于网络容错与资源分配。
Chromatic Feature Vectors for 2-Trees: Exact Formulas for Partition Enumeration with Network Applications
- 基于每三角恰好两色的约束，推导2-树的染色特征向量闭式解。
- 对θ图和扇形图分别得到斯特林数、斐波那契数等精确表达式，可线性或平方时间计算。
- 相比传统染色多项式，新特征能区分不同2-树结构，适用于分布式系统设计。
本文建立在双色三角约束下2-树的色特征向量的闭式枚举公式。该约束要求每个三角形使用恰好两种颜色，禁止单色和全异三角形，源于分布式系统中组件避免完全集中或孤立的需求。对于θ图Theta_n，证明r_k(Theta_n) = S(n-2, k-1)（k ≥ 3，S为第二类斯特林数），且r_2(Theta_n) = 2^(n-2) + 1，可在O(n)时间内计算。对于扇形图Phi_n，得出r_2(Phi_n) = F_{n+1}（Fibonacci数），并推导出r_k(Phi_n) = sum_{t=k-1}^{n-1} a_{n-1,t} * S(t, k-1)的显式公式，利用高效计算的二项式系数，每组件计算复杂度为O(n^2)。与经典染色多项式不同，该方法为所有n顶点2-树提供差异化的结构特征。尽管非完整图不变量，其特征通过关联斐波那契多项式、贝尔数与独立集计数，捕捉了有意义的结构属性。应用包括分层网络中的拜占庭容错、云中虚拟机分配及分布式密码学中的秘密共享协议。
原文摘要 · Abstract (English)
We establish closed-form enumeration formulas for chromatic feature vectors of 2-trees under the bichromatic triangle constraint. These efficiently computable structural features derive from constrained graph colorings where each triangle uses exactly two colors, forbidding monochromatic and rainbow triangles, a constraint arising in distributed systems where components avoid complete concentration or isolation. For theta graphs Theta_n, we prove r_k(Theta_n) = S(n-2, k-1) for k >= 3 (Stirling numbers of the second kind) and r_2(Theta_n) = 2^(n-2) + 1, computable in O(n) time. For fan graphs Phi_n, we establish r_2(Phi_n) = F_{n+1} (Fibonacci numbers) and derive explicit formulas r_k(Phi_n) = sum_{t=k-1}^{n-1} a_{n-1,t} * S(t, k-1) with efficiently computable binomial coefficients, achieving O(n^2) computation per component. Unlike classical chromatic polynomials, which assign identical features to all n-vertex 2-trees, bichromatic constraints provide informative structural features. While not complete graph invariants, these features capture meaningful structural properties through connections to Fibonacci polynomials, Bell numbers, and independent set enumeration. Applications include Byzantine fault tolerance in hierarchical networks, VM allocation in cloud computing, and secret-sharing protocols in distributed cryptography.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。