主题
Search

奇图


阶为 n 的奇图 O_n 是一个图,其顶点由 {1,...,2n-1}(n-1)-子集给出,使得当且仅当相关的子集是不相交的时,两个顶点通过边连接(Biggs 1993,Ex. 8f,p. 58)。需要注意的是,基于 {1,...,2n+1}n-子集定义奇图的约定有时也被使用,导致索引移动一位(例如,West 2000,Ex. 1.1.28,p. 17)。

根据使用普遍约定的奇图定义,O_n 中的节点数为 (2n-1; n-1),其中 (n; k) 是一个二项式系数。对于 n=1、2、...,前几个值是 1、3、10、35、126、... (OEIS A001700)。

OddGraphs

O_1 同构于 单例图O_2 同构于 三角形图 C_3O(3) 同构于 彼得森图 (Skiena 1990, p. 162)。克内泽图 K(n,k) 是奇图的推广,其中 O_n 对应于 K(2n-1,n-1)二部克内泽图 是奇图的 二部双图 的推广,其中 O_n 对应于 H(2n-1,n-1) (像 O_n 一样,它是 距离传递图;Brouwer et al. 1989, p. 222)。

O_n正则 的,顶点度n图直径n-1 (Biggs 1976)。O_n周长 对于 n>=4 为 6 (West 2000, p. 17; 将索引约定调整为更常见的基于 n-1 子集的定义)。

奇图是 距离传递 的,因此也是 距离正则 的。它们也是 自同构图 (Biggs 1976)。据推测,O_n1 类图,除了 n=3n 为 2 的幂的情况 (Fiorini and Wilson 1977)。

Balaban (1972) 展示了 n=4 和 5 的 哈密顿环,Meredith 和 Lloyd (1972, 1973) 找到了 n=6 和 7 的环,Mather (1976) 展示了 n=8哈密顿环 (Shields and Savage)。

由于奇图是 克内泽图 的一个特例,它的 独立数alpha(K(n,k)) 的值得出,如

 alpha(O_n)=(2n-2; n-2).

奇图在 Wolfram 语言 中实现为FromEntity[Entity["Graph", {"Odd", n]],并且小奇图的预计算属性实现为GraphData[{"Odd", n}].


另请参阅

完全图, 距离正则图, 距离传递图, 克内泽图, 奇顶点, 彼得森图

使用 Wolfram|Alpha 探索

参考文献

Balaban, A. T. "Chemical Graphs, Part XIII; Combinatorial Patterns." Rev. Roumaine Math. Pures Appl. 17, 3-16, 1972.Biggs, N. L. "Automorphic Graphs and the Krein Condition." Geom. Dedicata 5, 117-127, 1976.Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, p. 161, 1993.Brouwer, A. E. "Odd Graphs." http://www.win.tue.nl/~aeb/drg/graphs/Odd.html.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.DistanceRegular.org. "Odd Graphs." http://www.distanceregular.org/indexes/oddgraphs.html.Fiorini, S. and Wilson, R. Edge-Colourings of Graphs. Pittman, 1977.Mather, M. "The Rugby Footballers of Croam." J. Combin. Theory Ser. B 20, 62-63, 1976.Meredith, G. H. J. and Lloyd, E. K. "The Hamiltonian graphs O_4 to O_7." In Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972). Southend: Inst. Math. Appl., pp. 229-236, 1972.Meredith, G. H. J. and Lloyd, E. K. "The Footballers of Croam." J. Combin. Theory Ser. B 15, 161-166, 1973.Mütze, T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems." Not. Amer. Soc. 74, 583-592, 2024.Shields, I. and Savage, C. D. "A Note on Hamilton Cycles in Kneser Graphs." http://www.cybershields.com/publications/kneser3.pdf.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequence A001700/M2848 in "The On-Line Encyclopedia of Integer Sequences."West, D. B. "The Odd graph O_k." Exercise 1.1.28 in Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 17, 2000.

在 Wolfram|Alpha 上被引用

奇图

请按如下方式引用

Weisstein, Eric W. "Odd Graph." 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/OddGraph.html

主题分类