主題
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.tw/QuadraticEmbeddingConstant.html