Adjacency matrices of polarity graphs and of other C-4-free graphs of large size

作者：Abreu M; Balbuena C; Labbate D^*

来源：Designs, Codes and Cryptography, 2010, 55(2-3): 221-233.

DOI：10.1007/s10623-010-9364-1

• Adjacency
• Matrix
• Polarity
• Size

In this paper we give a method for obtaining the adjacency matrix of a simple polarity graph G(q) from a projective plane PG(2, q), where q is a prime power. Denote by ex(n; C-4) the maximum number of edges of a graph on n vertices and free of squares C-4. We use the constructed graphs G(q) to obtain lower bounds on the extremal function ex(n; C-4), for some n < q(2) + q + 1. In particular, we construct a C-4-free graph on n = q(2) - root q vertices and 1/2q(q(2) - 1) - 1/2 root q(q - 1) edges, for a square prime power q.

• 出版日期2010-5