主题
Search

Andrásfai 图

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本
AndrasfaiGraphs

该 n-Andrásfai 图是 3n-1 个节点上的循环图，其索引由与 1 (mod 3) 同余的整数 1, ..., 3n-1 给出。对于 n>1，Andrásfai 图的图直径为 2，并且 n-Andrásfai 图有 6(3n-1) 种 3-着色，所有这些着色在其自同构群下都是等价的 (Godsil 和 Royle 2001, p. 119)。

下表总结了前几个 Andrásfai 图。

n名称循环表示法
12-路径图Ci_2(1)
25-环图Ci_5(1)
34-莫比乌斯阶梯Ci_8(1,4)
44-Andrásfai 图Ci_(11)(1,4)
55-Andrásfai 图Ci_(14)(1,4,7)
66-Andrásfai 图Ci_(17)(1,4,7)

该 n-Andrásfai 图具有独立多项式

I_n(x)=1+(3n-1)x(x+1)^(n-1),

其对应的递推方程由下式给出

I_n(x)=(2x+3)I_(n-1)(x)-(x+1)(x+3)I_(n-2)(x)+(x+1)^2I_(n-3)(x),

参见

循环图

使用 探索

参考文献

Andrásfai, B. "Graphentheoretische Extremalprobleme." Acta Math. Acad. Sci. Hungar. 15, 413-438, 1964.Andrásfai, B. Introductory Graph Theory. Elmsford, NY: Pergamon Press, 1977.Brouwer, A. E. "Finite Graphs in Which the Point Neighbourhoods Are the Maximal Independent Sets." In From Universal Morphisms to Megabytes: A Baayen Space Odyssey. Amsterdam, Netherlands: Math. Centrum Wisk. Inform., pp. 231-233, 1994.Godsil, C. and Royle, G. "The Andrásfai Graphs," "Colouring Andrásfai Graphs," and "A Characterization." §6.10-6.12 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 118-123, 2001.Pach, J. "Graphs Whose Every Independent Set Has a Common Neighbour." Disc. Math. 31, 217-228, 1981.

在 上被引用

Andrásfai 图

请引用为

Weisstein, Eric W. "Andrásfai 图。" 来自 Web 资源。 https://mathworld.net.cn/AndrasfaiGraph.html

主题分类