主題
Search

半對稱圖


一個正則圖,它是邊傳遞的但不是頂點傳遞的,被稱為半對稱圖 (Marušič and Potočnik 2001)。相反,任何既是邊傳遞又是頂點傳遞的圖都被稱為對稱圖

注意,一個圖可能是邊傳遞的,但既不是頂點傳遞的也不是正則的。一個例子是Pasch 圖,因此它不是半對稱圖。其他例子包括星圖菱形十二面體圖菱形三十面體圖Schläfli 雙六圖

每個半對稱圖必然是二部圖,其兩部分大小相等,且自同構群在這兩部分上傳遞作用。在 n=1, 2, ... 個節點上的正則二部圖的數量是 1, 2, 1, 3, 1, 4, 1, 6, 1, ... (OEIS A087114)。

Folkman (1967) 證明了不存在階數為 2p 的半對稱圖,其中 p 是一個素數,並構造了一些階數為 2pq 的半對稱圖,其中 pq 是素數且 p=1 (mod q),包括所謂的 Folkman 圖。Folkman (1967) 還詢問是否存在階數為 30 的半對稱圖,Ivanov (1987) 隨後給出了否定回答。

SemisymmetricGraphs

不存在少於 20 個頂點的半對稱圖 (Skiena 1990, p. 186)。上面展示了半對稱圖的例子,並在下表中進行了總結。


另請參閱

立方半對稱圖, 邊傳遞圖, Folkman 圖, Gray 圖, Iofinova-Ivanov 圖, Ivanov-Ivanov-Faradjev 圖, Ljubljana 圖, 對稱圖, 頂點傳遞圖

使用 探索

參考文獻

Bouwer, I. A. "關於邊傳遞但非頂點傳遞的正則圖。" J. Combin. Th. Ser. B 12, 32-40, 1972.Du, S.-F. 和 Marus_ic_, D. "無限的雙本原半對稱圖族。" J. Graph Th. 32, 217-228, 1999.Du, S. 和 Xu, M. "階數為 2pq 的半對稱圖的分類。" Comm. Alg. 28, 2685-2715, 2000.Folkman, J. "正則線對稱圖。" J. Combin. Th. 3, 215-232, 1967.Ivanov, A. V. "關於邊傳遞但非頂點傳遞的正則圖。" 在 組合設計理論 (Ed. C. J. Colbourn and R. Mathon)。荷蘭阿姆斯特丹:North-Holland, pp. 273-285, 1987.Iofinova, M. E. and Ivanov, A. A. "雙本原立方圖。" 在 組合物件的代數理論研究。 pp. 123-134, 2002. (Vsesoyuz. Nauchno-Issled. Inst. Sistem. Issled., Moscow, pp. 137-152, 1985.)Klin, M. H. "關於邊傳遞但非頂點傳遞的圖。" 在 圖論中的代數方法,第一卷,第二卷:1978 年 8 月 24-31 日在塞格德舉行的會議論文集 (Ed. L. Lovász and V. T. Sós)。荷蘭阿姆斯特丹:North-Holland, pp. 399-403, 1981.Lipschutz, S. and Xu, M.-Y. "關於三價半對稱圖的無限族的註釋。" European J. Combin. 23, 707-711, 2002.Marušič, D. and Potočnik, P. "廣義 Folkman 圖的半對稱性。" European J. Combin. 22, 333-349, 2001.Marušič, D.; Pisanski, T.; and Wilson, S. "GRAY [原文如此] 圖的虧格為 7。" Europ. J. Combin. 26, 377-385, 2005.Skiena, S. 離散數學實現:使用 Mathematica 的組合數學和圖論。 美國馬薩諸塞州雷丁:Addison-Wesley, 1990.Sloane, N. J. A. 整數序列線上百科全書中的序列 A087114

在 中引用

半對稱圖

請引用為

Weisstein, Eric W. "半對稱圖。" 來自 Web 資源。 https://mathworld.tw/SemisymmetricGraph.html

主題分類