主題
Search

Paley圖

下載 Mathematica Notebook下載 Wolfram Notebook
PaleyGraphs

階為 q 的 Paley 圖是在 q 個節點上的圖，其中如果兩個節點的差在有限域 GF(q) 中是平方數，則這兩個節點相鄰。當 q=1 (mod 4) 時，該圖是無向的。因此，簡單 Paley 圖存在於階為 5, 9, 13, 17, 25, 29, 37, 41, 49, 53, 61, 73, 81, 89, 97, 101, 109, 113, 121, 125, 137, 149, 157, 169, ... (OEIS A085759)。

Paley 圖通常表示為 P(q) 或 QR(q) (Brouwer 等人，1989 年，第 10 頁)，其中 “QR” 代表二次剩餘。

分圓圖是 Paley 圖的三次類似物。

Paley 圖 P(q) 是強正則圖，引數為 (q,(q-1)/2,(q-5)/4,(q-1)/4) (Godsil 和 Royle 2001 年，第 221 頁)。對於 q 為素數，Paley 圖也是迴圈圖 Ci_q(l_1,...)，引數 l_i 由平方數（模 q）給出。

Paley 圖是自補、強正則、會議圖和哈密頓圖。所有 Paley 圖都是會議圖，但反之不成立（Godsil 和 Royle 2001 年，第 222 頁）。

特殊情況包括圈圖 C_5 (5-Paley)、 (2,1)-廣義四邊形 (9-Paley) 和 (25,15)-Paulus 圖 (25-Paley)。

17-Paley 圖是唯一最大的圖 G，使得 G 及其補圖都不包含 K_4 作為子圖 (Evans 等人，1981 年)。由此圖得出 Ramsey 數 Ramsey 數 R(4)=18。

Broere 等人（1988 年）表明，對於 P(q)，當 q 是素數的偶次冪時，團數和色數均為 sqrt(q)。J. B. Shearer 維護了一個 Paley 圖的獨立數表，適用於大小小於 7000 的圖，而 Brouwer 維護了一個 Paley 圖的獨立數和色數表，上限為 q=157。

另請參閱

Brouwer-Haemers 圖, 會議圖, 分圓圖, 有限域, Hadamard 圖, Hadamard 矩陣, Paley 構造, Paley 定理, Paulus 圖, 強正則圖

使用 探索

參考文獻

Baker, R. D.; Ebert, G. L.; Hemmeter, J.; Woldar, A. J. “平方階 Paley 圖中的最大團。” J. Statist. Plann. Inference 56, 33-38, 1996.Blokhuis, A. “關於具有平方差的 GF(q^2) 子集。” Indag. Math. 46, 369-372, 1984.Broere, I.; Döman, D.; and Ridley, J. N. “某些 Paley 圖的團數和色數。” Quaestiones Math. 11, 91-93, 1988.Brouwer, A. E. “Paley Graphs.” http://www.win.tue.nl/~aeb/drg/graphs/Paley.html.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. “會議矩陣和 Paley 圖。” 在 Distance Regular Graphs. New York: Springer-Verlag, p. 10, 1989.Brouwer, A. E. and van Lint, J. H. “強正則圖和部分幾何。” 在 Enumeration and Design: Papers from the conference on combinatorics held at the University of Waterloo, Waterloo, Ont., June 14-July 2, 1982 (Ed. D. M. Jackson and S. A. Vanstone). Toronto, Canada: Academic Press, pp. 85-122, 1984.DistanceRegular.org. “Paley Graphs.” http://www.distanceregular.org/indexes/paleygraphs.html.Evans, R. J.; Pulham, J. R.; and Sheehan, J. “關於某些圖中包含的完全子圖的數量。” J. Combin. Th. Ser. B 30, 364-371, 1981.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, pp. 221-222, 2001.Jones, G. A. “Paley 和 Paley 圖。” 在 Isomorphisms, Symmetry and Computations in Algebraic Graph Theory: Pilsen, Czech Republic, October 3-7, 2016 (Ed. G. A. Jones, I. Ponomarenko, and J. Širáň). Cham, Switzerland: Springer Nature, pp. 155-183, 2020.Muzychuk, M. E. “Paley 圖和分圓方案的自同構群。” 在 Isomorphisms, Symmetry and Computations in Algebraic Graph Theory: Pilsen, Czech Republic, October 3-7, 2016 (Ed. G. A. Jones, I. Ponomarenko, and J. Širáň). Cham, Switzerland: Springer Nature, pp. 185-194, 2020.Seidel, J. J. “圖和二圖。” 在 Proc. 5th Southeast Conf. Comb., Graph Th., Comp. (Ed. F. Hoffman et al.). Winnipeg, Canada: Utilitas Mathematica Pub., pp. 125-143, 1974.Shearer, J. B. “Paley 圖的獨立數。” http://www.research.ibm.com/people/s/shearer/indpal.html.Sloane, N. J. A. 序列 A085759 在 “整數序列線上百科全書” 中。

在 中引用

Paley圖

請按如下方式引用

Weisstein, Eric W. “Paley 圖。”來自 Web 資源。 https://mathworld.tw/PaleyGraph.html

主題分類