主題
Search

圖的虧格


G 的虧格 gamma(G) 是必須新增到平面上的最小手柄數,以便在沒有任何交叉的情況下嵌入該圖。虧格為 0 的圖可以嵌入到平面中,並且被稱為平面圖。下表總結了具有特定虧格值的圖類的名稱(參見 West 2000, p. 266)。

每個圖都有一個虧格 (White 2001, p. 53)。

最小的雙環面圖有 8 個頂點,並且恰好有 15 個 8 節點的雙環面圖。

沒有頂點數少於或等於 8 的椒鹽捲餅圖。

S_gamma 為虧格為 gamma 的曲面。那麼,如果 gamma(G)=k 對於 k>0,則 GS_k 中有一個嵌入,但不在 S_i 中,對於 i<k。此外,G 嵌入在 S_j 中,對於所有 j>=k,這可以透過向 GS_k 中的嵌入新增 j-k 個手柄來看到(White 2001, p. 52)。

G 的虧格滿足

 gamma(G)<=m
(1)

其中 mG邊數(White 2001, p. 53)。

不連通圖的虧格是其連通分量的虧格之和 (Battle et al. 1962, White 2001, p. 55),而連通圖的虧格是其的虧格之和 (Battle et al. 1962; White 2001, p. 55; Stahl 1978)。

根據 Battle et al. (1962) 的結果,nK_5 的不相交併集(或 nK_(3,3) 的不相交併集)是虧格為 n-1 的圖的停用次子式。類似地,nK_5K_(3,3),使得某些共享一個頂點並且其塊是 K_5_K3,3,是虧格為 n-1 的圖的停用次子式。

Duke 和 Haggard (1972; Harary et al. 1973) 給出了所有頂點數少於或等於 8 的圖的虧格的判據。定義雙環面圖

B_1=K_8-K_3
(2)
B_2=K_8-(2K_2 union P_3)
(3)
B_3=K_8-K_(2,3),
(4)

其中 G-H 表示 G 減去 H 的邊。那麼對於 K_8 的任何子圖 G

1. 如果 G 不包含庫拉托夫斯基圖(即,K_5K_(3,3)),則 gamma(G)=0

2. 如果 G 包含庫拉托夫斯基圖(即,是非平面圖),但不包含任何 B_i,對於 i=1,2,3,則 gamma(G)=1

3. 如果 G 包含任何 B_i,對於 i=1,2,3,則 gamma(G)=2

完全圖 K_n 的虧格為

 gamma(K_n)=[((n-3)(n-4))/(12)]
(5)

對於 n>=3,其中 [x]向上取整函式(Ringel 和 Youngs 1968;Harary 1994, p. 118)。對於 n=1, 2, ... 的值分別為 0, 0, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 8, 10, ... (OEIS A000933)。

完全二分圖 K_(m,n) 的虧格為

 gamma(K_(m,n))=[((m-2)(n-2))/4]
(6)

(Ringel 1965;Beineke 和 Harary 1965;Harary 1994, p. 119)。

超立方體 Q_n 的虧格為

 gamma(Q_n)=1+(n-4)2^(n-3)
(7)

(Ringel 1955;Beineke 和 Harary 1965;Harary et al. 1988;Harary 1994, p. 119)。對於 n=1, 2, ... 的值分別為 0, 0, 0, 1, 5, 17, 49, 129, ... (OEIS A000337)。


另請參閱

環秩, 雙環面圖, 圖的交叉數, 平面圖, 椒鹽捲餅圖, 直線交叉數, 環面圖

使用 探索

參考文獻

Battle, J.; Harary, F.; and Kodama, Y. "每個具有九個點的平面圖都有一個非平面補圖。" 美國數學學會公報 68, 569-571, 1962.Battle, J.; Harary, F.; Kodama, Y.; and Youngs, J. W. T. "圖的虧格的可加性。" 美國數學學會公報 68, 565-568, 1962.Beineke, L. W. and Harary, F. "涉及圖的虧格及其厚度的不等式。" 格拉斯哥數學協會會刊 7, 19-21, 1965.Beineke, L. W. and Harary, F. "n-立方體的虧格。" 加拿大數學雜誌 17, 494-496, 1965.Duke, R. A.; and Haggard, G. "K_8 的子圖的虧格。" 以色列數學雜誌 11, 452-455, 1972.Harary, F. 圖論。 裡丁,馬薩諸塞州:Addison-Wesley,1994 年。Harary, F.; Kainen, P. C.; Schwenk, A. J.; and White, A. T. "一個非三角剖分的最大環面圖。" 數學斯堪的納維亞 33, 108-112, 1973.Harary, F. and Kodama, Y. "關於 n-連通圖的虧格。" 數學基礎 54, 7-13, 1964.Harary, F. and Palmer, E. M. 圖形計數。 紐約:Academic Press,p. 225, 1973 年。Harary, F. and Palmer, E. M. "圖計數問題綜述。" 在組合理論綜述 (J. N. Srivastava 編輯) 中。 阿姆斯特丹:North-Holland,pp. 259-275, 1973 年。Harary, F.; Hayes, J. P.; and Wu, H.-J. "超立方體圖理論綜述。" 計算機數學應用 15, 277-289, 1988.Heawood, P. J. "地圖著色定理。" 季刊數學雜誌 24, 332-338, 1890.Heffter, L. "Über das Problem der Nachbargebiete." 數學年鑑 38, 477-508, 1891.Jungerman, M. and Ringel, G. "n-八面體的虧格:規則情況。" 圖論雜誌 2, 69-75, 1978.Mayer, J. "Le problème des régions voisines sur les surfaces closes orientables." 組合理論雜誌 6, 177-195, 1969.Mohar, B. "將圖嵌入曲面的障礙。" 離散數學 78, 135-142, 1989.Ringel, G. 平面和圖上的著色問題。 柏林:德國科學出版社,1962 年。Ringel, G. "完全偶圖的虧格。" 漢堡大學數學研討會論文集 28, 139-150, 1965.Ringel, G. "關於 n 維立方體和立方體網格上的三個組合問題。" 漢堡大學數學研討會論文集 20, 10-19, 1955.Ringel, G. and Youngs, J. W. T. "希伍德地圖著色問題的解。" 美國國家科學院院刊 60, 438-445, 1968.Ringel, G. and Youngs, J. W. T. "關於希伍德猜想的評論。" 在圖論中的證明技術 (F. Harary 編輯) 中。 紐約:Academic Press,1969 年。Skiena, S. 離散數學的實現:使用 Mathematica 的組合學和圖論。 裡丁,馬薩諸塞州:Addison-Wesley,p. 251, 1990 年。Sloane, N. J. A. 序列 A000337/M3874 和 A000933/M0503 在 "整數序列線上百科全書" 中。Stahl, S. "圖的嵌入——綜述。" 圖論雜誌 2, 275-298, 1978.West, D. B. "更高虧格的曲面。" 圖論導論,第二版。 恩格爾伍德崖,新澤西州:Prentice-Hall,pp. 266-269, 2000 年。White, A. T. "圖論中的嵌入問題。" 在曲面上的群圖:互動和模型(A. T. White 編輯)的第 6 章中。 荷蘭阿姆斯特丹:Elsevier,pp. 49-72, 2001 年。

在 中被引用

圖的虧格

引用為

韋斯坦因,埃裡克·W. "圖的虧格。" 來自 Web 資源。 https://mathworld.tw/GraphGenus.html

主題分類