Polarity graphs revisited

Bachratý, Martin and Širáň, Jozef (2015). Polarity graphs revisited. Ars Mathematica Contemporanea, 8(1) pp. 55–67.

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].

Viewing alternatives

Item Actions

Export

You can export this page using these formats