主題
Search

頂點傳遞圖


頂點傳遞圖,有時也稱為節點對稱圖 (Chiang and Chen 1995),是一個,其任意一對頂點在它的自同構群的某個元素下是等價的。更明確地說,頂點傳遞圖是其自同構群傳遞的圖 (Holton and Sheehan 1993, p. 27)。通俗地說,如果每個頂點的區域性環境相同,使得任何頂點都無法根據其周圍的頂點和邊與其他頂點區分開來,則該圖是頂點傳遞的。

表徵頂點傳遞圖的另一種方式是將其定義為自同構群具有單個群軌道(即,其自同構群的軌道長度是單個數字)的圖。

可以使用以下Wolfram 語言來測試圖是否為頂點傳遞圖:VertexTransitiveGraphQ[g]。

如果圖中每條都具有相同的區域性環境,使得任何邊都無法與其他邊區分開來,則稱該圖是邊傳遞的。無向連通圖邊傳遞的,當且僅當其線圖是頂點傳遞的。

所有頂點傳遞圖都是正則的,但反之不一定成立。正則圖如果是邊傳遞的但不是頂點傳遞的,則稱為半對稱圖。相反,任何既是邊傳遞又是頂點傳遞的圖都稱為對稱圖 (Holton and Sheehan 1993, pp. 209-210)。

洛瓦茲猜想斷言,毫無例外,每個連通頂點傳遞圖都是可追蹤的。

此外,恰好有五個已知的連通非哈密頓頂點傳遞圖,即路徑圖 P_2彼得森圖 F_(010)A考克斯特圖 F_(028)A三角形替換彼得森圖,以及三角形替換考克斯特圖。正如 Gould (1991) 引用 Bermond (1979) 所述,Thomassen 猜想所有其他連通頂點傳遞圖都是哈密頓圖 (cf. Godsil and Royle 2001, p. 45; Mütze 2024)。

Vertex-TransitiveGraphs

具有 n=1, 2, ... 個節點的頂點傳遞簡單圖的數量為 1, 2, 2, 4, 3, 8, 4, 14, 9, ... (OEIS A006799; McKay 1990; Colbourn and Dinitz 1996)。

Vertex-TransitiveConnectedGraphs

對於 n=1, 2, ...,具有 n 個節點的連通頂點傳遞簡單圖的數量為 1, 1, 1, 2, 2, 5, 3, 10, 7, ... (OEIS A006800; McKay and Royle 1990)。


另請參閱

弧傳遞圖, 自同構群, 凱萊圖, 三次頂點傳遞圖, 邊傳遞圖, 福爾克曼圖, 格雷圖, 群軌道, 非哈密頓圖, 非哈密頓頂點傳遞圖, 四次頂點傳遞圖, 半對稱圖, 對稱圖, 傳遞群

使用 探索

參考文獻

Bermond, J.-C. "Hamiltonian Graphs." Ch. 6 in Selected Topics in Graph Theory (Ed. L. W. Beineke and R. J. Wilson). London: Academic Press, pp. 127-167, 1979.Chiang, W.-K. and Chen, R.-J. "The (n,k)-Star Graph: A Generalized Star Graph." Information Proc. Lett. 56, 259-264, 1995.Colbourn, C. J. and Dinitz, J. H. (Eds.). CRC Handbook of Combinatorial Designs. Boca Raton, FL: CRC Press, p. 649, 1996.Godsil, C. and Royle, G. "Hamilton Paths and Cycles." C§3.6 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 45-47, 2001.Gould, R. J. "Updating the Hamiltonian Problem--A Survey." J. Graph Th. 15, 121-157, 1991.Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.Lauri, J. and Scapellato, R. Topics in Graph Automorphisms and Reconstruction. Cambridge, England: Cambridge University Press, 2003.Lovász, L. Problem 11 in "Combinatorial Structures and Their Applications." In Proc. Calgary Internat. Conf. Calgary, Alberta, 1969. London: Gordon and Breach, pp. 243-246, 1970.McKay, B. D. and Praeger, C. E. "Vertex-Transitive Graphs Which Are Not Cayley Graphs. I." J. Austral. Math. Soc. Ser. A 56, 53-63, 1994.McKay, B. D. and Royle, G. F. "The Transitive Graphs with at Most 26 Vertices." Ars Combin. 30, 161-176, 1990.Mütze, T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems." Not. Amer. Soc. 74, 583-592, 2024.Royle, G. "Cubic Symmetric Graphs (The Foster Census): Hamiltonian Cycles." http://school.maths.uwa.edu.au/~gordon/remote/foster/#hamilton.Royle, G. "Transitive Graphs." http://school.maths.uwa.edu.au/~gordon/trans/.Sloane, N. J. A. Sequences A006799/M0302 and A006800/M0345 in "The On-Line Encyclopedia of Integer Sequences."Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

在 上被引用

頂點傳遞圖

請引用為

Weisstein, Eric W. "頂點傳遞圖。" 來自 Web 資源。 https://mathworld.tw/Vertex-TransitiveGraph.html

學科分類