scientific article; zbMATH DE number 166086

Let \(G\) be a simple undirected graph without loops. We say that \(G\) has property \(P(m,n,k)\) if for any set of \(m+n\) distinct vertices of \(G\) there are at least \(k\) other vertices, each of which is adjacent to the first \(m\) vertices but not adjacent to any of the latter \(n\) vertices. Some properties of graphs having property \(P(m,n,k)\) are presented. Moreover, for a prime number \(p\) of the form \(4t+1\) the following graph \(G_ p\) is called a Paley graph: The vertices of \(G_ p\) are elements of the Galois field \(\text{GF}(p)\); two vertices \(i,j\) are joined by an edge if and only if \(i-j\equiv y^ 2\pmod p\) for some \(y\) of \(\text{GF}(p)\). The conjecture of \textit{L. Caccetta}, \textit{K. Vijayan} and \textit{W. D. Wallis} [On strongly accessible graphs, Ars Comb. 17--A, 93- 102 (1984; Zbl 0539.05051)] that \(G_ p\) has property \(P(2,2,1)\) for all \(p\geq 61\) is confirmed. In addition, it is proved that: \(G_ p\) has property \(P(2,2,k)\) for every \(p>(5+2\sqrt{4k+6})^ 2\), \(G_ p\) has property \(P(n,n,1)\) for every \(p>((2n-3)^{2n-1}+4)^ 2\), and \(G_ p\) has property \(P(1,2,k)\) for every \(p>(1+2\sqrt{2k})^ 2\).

Recommendations

Cited in

(14)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4033699)