### Polarity graphs revisited

#### Abstract

Polarity graphs, also known as Brown graphs, and their minor modifications are the largest currently known graphs of diameter 2 and a given maximum degree *d* such that *d* − 1 is a prime power larger than 5. In view of the recent interest in the degree-diameter problem restricted to vertex-transitive and Cayley graphs we investigate ways of turning the (non-regular) polarity graphs to large *vertex-transitive* graphs of diameter 2 and given degree.

We review certain properties of polarity graphs, giving new and shorter proofs. Then we show that polarity graphs of maximum even degree *d* cannot be spanning subgraphs of vertex-transitive graphs of degree at most *d* + 2. If *d* − 1 is a power of 2, there are two large vertex-transitive induced subgraphs of the corresponding polarity graph, one of degree *d* − 1 and the other of degree *d* − 2. We show that the subgraphs of degree *d* − 1 cannot be extended to vertex-transitive graphs of diameter 2 by adding a relatively small non-edge orbital. On the positive side, we prove that the subgraphs of degree *d* − 2 can be extended to the largest currently known Cayley graphs of given degree and diameter 2 found by Šiagiová and the second author [*J. Combin. Theory Ser. B* **102** (2012), 470–473].

#### Keywords

DOI: https://doi.org/10.26493/1855-3974.527.74e

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications