主题
Search

二次嵌入常数

有限简单连通图 G 在 n 个顶点上的二次嵌入常数 QEC(G) 定义为乘积 vDv 在所有满足 v.v=1 和 sum_(i=1)^(n)v_i=0 的实数 n 维向量 v 上的最大值，其中 D 是 图距离矩阵 (Obata and Zakiyyah 2018, Obata 2022, Choudhury and Nandi 2023)。Obata 和 Zakiyyah (2018) 给出了顶点数为 5 或更少的连通图的二次嵌入常数（尽管对于 5 个节点的第 12 个图，即风筝图，给出的值是不正确的）。

以下给出 单点图 K_1 (Obata and Zakiyyah 2018), 完全图 K_n，其中 n>=2 (Obata and Zakiyyah 2018, Obata 2022), 完全二分图 K_(m,n) (Obata and Zakiyyah 2018, Obata 2022), 圈图 C_n (Obata and Zakiyyah 2018, Obata 2022), 路径图 P_n，其中 n>=2 (Młotkowski 2022, Obata 2022) 和 轮图 (E. Weisstein, Jul. 3, 2023) 的二次嵌入常数：

QEC(K_1)=0
(1)
QEC(K_n)=-1
(2)
QEC(K_(m,n))=(2(m-1)(n-1)-2)/(m+n)
(3)
QEC(C_n)={0 for n even; -1/4sec^2(pi/n) for n odd
(4)
QEC(P_n)=-(1+cos(pi/n))^(-1)
(5)
QEC(W_n)={0 for n odd; -4sin^2(pi/(2(n-1))) for n even.
(6)

Obata (2022) 给出了一般完全 k 部图的二次嵌入常数。

通过从完全图中删除两个或更多不相交子集获得的任何图的二次嵌入常数都等于 0 (Obata and Zakiyyah 2018)。这包括 方图 C_4, 轮图 W_5, 八面体图 K_(2,2,2), 2×3 后图 K_(1,1,2,2), 16-胞 图 K_(2,2,2,2), 和完全 k 部图 K_(1,2,2,2), K_(1,1,1,2,2) 等。

每个都具有两个或更多顶点的图 G_1, G_2, ... 的 图笛卡尔积 的二次嵌入常数为 QEC(G_1 square G_2 square ...)=0 (Obata 2022)。

对于 图距离矩阵 D 具有相等行和的连通图，二次嵌入常数由 D 的第二大 特征值 给出 (Obata and Zakiyyah 2018)。

对于 QEC(G)<=0 成立的连通图称为 二次可嵌入图。

另请参阅

图距离矩阵, 二次可嵌入图

使用 探索

参考文献

Choudhury, P. N. 和 Nandi, R. “图的二次嵌入常数：界限和距离谱”。2023 年 6 月 27 日。 https://arxiv.org/abs/2306.15589。Młotkowski, W. “路径图的二次嵌入常数。”线性代数及其应用 644, 95-107, 2022.Obata, N. “非 QE 类的完全多部图。”2022 年 6 月 12 日。 https://arxiv.org/abs/2206.05848。Obata, N. 和 Zakiyyah, A. Y. “图的距离矩阵和二次嵌入。”电子图论应用杂志 6, 37-60, 2018.Schoenberg, I. J. “度量空间和正定函数。”美国数学学会汇刊 44, 522-536, 1938.

请引用为

Weisstein, Eric W. “二次嵌入常数。” 来自 Web 资源。 https://mathworld.net.cn/QuadraticEmbeddingConstant.html