Paley graphs satisfy all first-order adjacency axioms
Paley graphs satisfy all first-order adjacency axioms
复制标题
佩利图满足所有一阶邻接公理
DOI：
10.1002/jgt.3190050414
复制
发表时间：
1981
期刊：
影响因子：
--
通讯作者：
F. Harary
中科院分区：
文献类型：
--
作者：
A. Blass;G. Exoo;F. Harary
一个图满足公理n，如果对于它的任意2n个点的序列，有另一个点与第一个n相邻，而不与最后的n相邻。我们证明了，对于每个n，所有足够大的Paley图满足公理n。由此，我们立即得出结论，图的一些性质不是一阶的，包括自补性和正则性。
A graph satisfies Axiom n if, for any sequence of 2n of its points, there is another point adjacent to the first n and not to any of the last n. We show that, for each n, all sufficiently large Paley graphs satisfy Axiom n. From this we conclude at once that several properties of graphs are not first order, including self-complementarity and regularity.