zbMATH — the first resource for mathematics

On the adjacency properties of Paley graphs. (English) Zbl 0777.05095
A finite graph \((V,E)\) is said to have property \(P(m,n,k)\) and to belong to \({\mathcal G}(m,n,k)\) if for any set of \(m+n\) distinct vertices there are at least \(k\) other vertices each of which is adjacent to the first \(m\) vertices but not adjacent to any of the last \(n\) vertices. This paper contains several results about this class of graphs. For example:
Theorem 2.2. Let \((V,E)\in{\mathcal G}(2,2,k)\). Then \[ | V|\geq\begin{cases} 34 & \text{ if } k=1 \\ 8k+25 & \text{ if } k\geq 3 \text{ and }k \text{ odd} \\ 8k+21 & \text{ otherwise } \end{cases} \] with equality possible only if \((V,E)\) is a strongly regular graph with parameters \((4t+1,2t,t- 1,t)\).
Theorem 4.2. Let \(q\equiv 1\pmod 4\) be a prime power and \(k\) a positive integer. If \[ q>\{(t-3)2^{t-1}+2\}\sqrt q+(t+2k-1)2^{t-1}-1, \] then the Paley graph \(G_ q\) is in \({\mathcal G}(m,n,k)\) for all \(m,n\) with \(m+n\leq t\).

05C99 Graph theory
11T99 Finite fields and commutative rings (number-theoretic aspects)
05E30 Association schemes, strongly regular graphs
Paley graph
Full Text: DOI
[1] Ananchuen, Aust. J. Comb. 6 pp 155– (1992)
[2] Blass, J. Graph Theory 3 pp 225– (1979)
[3] Blass, J. Graph Theory 5 pp 435– (1981)
[4] Random Graphs. Academic Press, London (1985).
[5] and , Graph Theory with Applications. MacMillan, London (1977).
[6] Graph theory in network designs and analysis. Recent Stud. Graph Theory (1989) 26–63.
[7] Caccetta, ARS Comb. 19A pp 287– (1985)
[8] Caccetta, ARS Comb. 21A pp 21– (1986)
[9] Caccetta, ARS Comb. 17A pp 93– (1984)
[10] Exoo, J. Graph Theory 5 pp 371– (1981)
[11] Exoo, Discrete Math. 29 pp 25– (1980)
[12] Frucht, Ann. N.Y. Acad. Sci. 175 pp 159– (1970) · Zbl 0228.05101
[13] and , Finite Fields, Addison-Wesley, London (1983).
[14] Equations over Finite Fields, An Elementary Approach. Lecture Notes in Mathematics, Vol. 536. Springer-Verlag, Berlin (1976). · Zbl 0329.12001
[15] , and , Combinatorics Room Squares, Sum-Free Sets, Hadamard Matrices. Lecture Notes in Mathematics, Vol. 292. Springer-Verlag, Berlin (1972). · Zbl 1317.05003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.