主题
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)。


另请参阅

弧传递图, 自同构群, 凯莱图, 三次顶点传递图, 边传递图, 福尔克曼图, 格雷图, 群轨道, 非哈密顿图, 非哈密顿顶点传递图, 四次顶点传递图, 半对称图, 对称图, 传递群

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 上被引用

顶点传递图

请引用为

Weisstein, Eric W. "顶点传递图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Vertex-TransitiveGraph.html

学科分类