阶为 
的 Paley 图是在 
个节点上的图，其中如果两个节点的差在有限域 GF(
) 中是平方数，则这两个节点相邻。当 
时，该图是无向的。因此，简单 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 图通常表示为 
或 
(Brouwer 等人，1989 年，第 10 页)，其中 “QR” 代表二次剩余。
分圆图是 Paley 图的三次类似物。
Paley 图 
是强正则图，参数为 
(Godsil 和 Royle 2001 年，第 221 页)。对于 
为素数，Paley 图也是循环图 
，参数 
由平方数（模 
）给出。
Paley 图是自补、强正则、会议图和哈密顿图。所有 Paley 图都是会议图，但反之不成立（Godsil 和 Royle 2001 年，第 222 页）。
特殊情况包括圈图 
(5-Paley)、 
-广义四边形 (9-Paley) 和 
-Paulus 图 (25-Paley)。
17-Paley 图是唯一最大的图 
，使得 
及其补图都不包含 
作为子图 (Evans 等人，1981 年)。由此图得出 Ramsey 数 Ramsey 数 
。
Broere 等人（1988 年）表明，对于 
，当 
是素数的偶次幂时，团数和色数均为 
。J. B. Shearer 维护了一个 Paley 图的独立数表，适用于大小小于 7000 的图，而 Brouwer 维护了一个 Paley 图的独立数和色数表，上限为 
。
另请参阅
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(
) 子集。” 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.net.cn/PaleyGraph.html
主题分类
