主題
Search

對稱圖


對稱圖是一個,它既是邊傳遞的又是頂點傳遞的(Holton 和 Sheehan 1993, p. 209)。

然而,必須謹慎對待這個定義,因為弧傳遞圖或 1-弧傳遞圖有時也被稱為對稱圖(Godsil 和 Royle 2001, p. 59)。當存在一些圖,它們在頂點傳遞邊傳遞的意義上是對稱的,但不是弧傳遞的,這可能會特別令人困惑。換句話說,存在這樣的圖,其中任何邊都可以對映到任何其他邊——但只有兩種可能的方式中的一種。Tutte (1966) 首先考慮了這類圖,他表明任何這樣的圖都必須是偶數度的正則圖。Bouwer (1970) 給出了第一個例子,他最小的例子有 54 個頂點,是四次圖。Dolye (1976) 和 Holt (1981) 隨後和獨立地發現了一個美麗的 27 個頂點的四次對稱圖,稱為Doyle 圖(或有時稱為 Holt 圖),它不是弧傳遞的。這個圖可以從 Bouwer 的 54 頂點圖透過識別直徑相對的頂點對獲得(Doyle 1998)。

一個正則圖,它是邊傳遞的但不是頂點傳遞的,被稱為半對稱圖

對稱圖的圖補線圖都不一定是對稱的。

SymmetricGraphs

對稱圖總是正則圖。節點數為 n=1, 2, ... 的對稱圖的數量分別為 1, 2, 2, 4, 3, 7, 3, 9, ...,上面說明了其中的一些。這些是完全圖 K_3; 圈圖 C_4, K_4; C_5, K_5; C_6, 迴圈圖 Ci_6(1,3), Ci_6(2), 八面體圖, 以及 K_6

下表給出了其他命名的對稱圖的列表。


參見

弧傳遞圖, 自同構群, Bouwer 圖, 三次對稱圖, Doyle 圖, 邊傳遞圖, 圖自同構, 單點陣圖, 四次對稱圖, 頂點傳遞圖

在 上探索

參考文獻

Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231-237, 1970.Chao, C.-Y. "On the Classification of Symmetric Graphs with a Prime Number of Vertices." Trans. Amer. Math. Soc. 158, 247-256, 1971.Cheng, Y. and Oxley, J. "On Weakly Symmetric Graphs of Order Twice a Prime." J. Combin. Th. Ser. B 42, 196-211, 1987.Doyle, P. G. On Transitive Graphs. Senior Thesis. Cambridge, MA, Harvard College, April 1976.Doyle, P. "A 27-Vertex Graph That Is Vertex-Transitive and Edge-Transitive But Not L-Transitive." October 1998. http://hilbert.dartmouth.edu/~doyle/docs/bouwer/bouwer/bouwer.html.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, 2001.Harary, F. "Symmetric Graphs" and "Highly Symmetric Graphs." Graph Theory. Reading, MA: Addison-Wesley, pp. 171-175, 1994.Holt, D. F. "A Graph Which Is Edge Transitive But Not Arc Transitive." J. Graph Th. 5, 201-204, 1981.Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.Praeger, C.; Wang, R. J.; and Xu, M. Y. "Symmetric Graphs of Order a Product of Two Distinct Primes." J. Combin. Th. Ser. B 58, 299-318, 1993.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequence A087145 in "The On-Line Encyclopedia of Integer Sequences."Tutte, W. T. Connectivity in Graphs. Toronto, CA: University of Toronto Press, 1966.Wang, R. J. and Xu, M. Y. "A Classification of Symmetric Graphs of Order 3p." J. Combin. Th. Ser. B 58, 197-216, 1993.

在 上引用

對稱圖

請引用為

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

學科分類