A geometric characterization of the line graph of a projective plane

AbstractThe line graph of a graph G is defined to be the graph whose vertices are the edges of G, two vertices being adjacent if and only if the corresponding edges of G have a common vertex. If π is a projective plane of order n, then the bipartite graph of π, denoted by G(π), is the graph whose vertices are the 2(n2+n+1) points and lines of π, two vertices of G(π) being adjacent if and only if one is a point and the other is a line containing the point. The line graph of G(π) will be denoted by L(π). A characterization of the class {L(π)} in terms of the eigenvalues of the adjacency matrix of L(π) has been given by Hoffman. An alternative characterization of the class {L(π)} is presented here. If d(x, y) denotes the distance between two vertices x and y and Δ(x, y) denotes the number of vertices adjacent to both x and y, then G=L(π) has the following properties: (b1) The number of vertices in G is (n+1)(n2+n+1). (b2) G is connected and regular of valence 2n. (b3) Δ(x, y)=n−1 if d(x, y)=1 (b4) Δ(x, y)=1 if d(x, y)=2. (b5) If d(x, y)=2, the number of vertices z, such that d(x, z)=1 and d(y, z)=2, is at most n−1. In this paper we show that any graph G with no loops and no multiple edges having the properties (b1)−(b5) must be the line graph of a projective plane of order n