主題
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.tw/AndrasfaiGraph.html

主題分類